Description

Now I will introduce a pretty tree which is called Stern-Brocot Tree, because it was discovered independently by Moritz Stern, a German mathematician, and Achille Brocot, a French clockmaker. The idea is to start with the two fractions (0/1,1/0) and then to repeat the following operation as many times as desired:

Insert (m+m')/(n+n') between two adjacent fractions m/n and m'/n'.

The new fraction (m+m')/(n+n') is called the mediant of m/n and m'/n'.

For example, the first step gives us one way entry between 0/1 and 1/0,

0/1, 1/1 , 1/0

And the next gives two more,

0/1, 1/2, 1/1, 2/1, 1/0

Then will be 4,8,16 more, like the follow picture:

Well, my question is giving you an arbitrary fraction, could you find this fraction in Stern-Brocot Tree ?

Input

The first line is the number of the fractions n The next n line is the fractions, the numerator will be between 1 to 10^100,inclusive; the denominator will be between 1 to 10^100 inclusive.

Output

If the fraction could be found in Stern-Brocot Tree , then you should output “Yes”, else you should output “No”.

Sample

Input

3
1/1
2/1
2/2

Output

Yes
Yes
No

Hint

I consider that two fractions are same while their numerators is same and their denominator are also same, eg: 2/2 is not equal to 1/1.

Source: guoxu