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 ?


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).


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.


6 2
5 1
3 3


hide comments
lumaks_69: 2022-02-11 11:10:40

nice problem

nadstratosfer: 2017-09-07 05:36:04

Seemed hard at first, then almost too simple, then again almost impossible given the constraints, then got AC. Nice one =)

Raghav Aggiwal Again: 2015-08-01 21:36:56

Loved it!

Mayank Ladia: 2015-02-11 18:22:19

Nice one :) ....

Samar Holkar: 2014-07-07 19:40:07

Beautiful Logic.....just generalise the numbers....

Bharath Reddy: 2014-03-28 08:27:33

Nice problem... Made me think

acheron: 2014-02-11 16:18:19

@anurag Start with (1, 1) then -> (1, 2) -> (1, 4) -> (2, 4) -> (4, 4) (we only used duplications).

Last edit: 2014-02-11 16:19:06
anurag garg: 2014-02-07 16:05:32

I guess weak test cases I think for 4 4 ans should be no but my AC soln gives Yes
correct me if i am wrong..

Last edit: 2014-02-07 16:06:16
Bhavik: 2014-02-07 14:26:37

try some test cases on you own and you will find the method to solve it...:)
but weak test cases....
for(4,8) both Y,N gets accepted...

Last edit: 2014-02-07 16:05:16
Jumpy: 2014-02-04 06:49:00

after a long time used something new logic

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