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 = 10¹⁸).

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