TWOGAME - Two Game

no tags 

Alice started playing a new simple game. She starts with the pair of integers (1, 1) and then she may a) duplicate one of the numbers or b) subtract the smaller number from the bigger one. So the game may proceed as follows: she starts with (1, 1), then she moves to (2, 1), then to (4, 1), then to (4, 2), then to (8, 2), then to (6, 2), etc.

She is now wondering if given an arbitrary pair of positive integers (A, B), will she be able to reach at this pair using the proceduce described above ?

Input

The first line contains a single positive integer T (T = 500), denoting the number of test cases to solve. Each test case consists of a single line containing two positive integers A, B (A, B = 1018).

Output

For each test case print a single line with the character Y if it is possible for Alice to reach the given pair or N if it is impossible.

Example

Input:
3
6 2
5 1
3 3

Output:
Y
Y
N

hide comments
Apoorv Jindal: 2013-12-19 16:04:46

The question text guarantees for a necessary condition but isn't enough to justify that condition to be sufficient.I guess one more operation of adding one number to the other must be added to the problem description.

jaanwar: 2013-12-18 21:23:49

plz suggest any tricky case , i hv made gud algo. , works perfectly on every case i hv taken ..... plz


Added by:acheron
Date:2013-12-17
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64