Subtraction Game

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian as well.
Two players are playing a game. The game is played on a sequence of positive integer pairs. The players make their moves alternatively. During his move the player chooses a pair and decreases the larger integer in the pair by a positive multiple of the smaller integer in the pair in such a way that both integers in the pair remain positive. If two numbers in some pair become equal then the pair is removed from the sequence. The player who can not make any move loses (or in another words the player who encounters an empty sequence loses). Given the sequence of positive integer pairs determine whether the first player can win or not (assuming that both players are playing optimally).
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
Each test starts with an integer N denoting the number of pairs. Each of the next N lines contains a pair of positive integers.
Output
For each test case, output a single line containing "YES" if the first player can win and "NO" otherwise.
Constraints
 1 ≤ T ≤ 100
 1 ≤ N ≤ 100
 All other integers are between 1 to 10^{8}
 The integers in each pair will be different
Example
Input: 3 1 2 3 2 4 5 5 6 2 2 3 3 5 Output: NO NO YES
Explanation
Example case 1. The first player don't have any choice other subtracting 2 from 3. So during the turn of the second player integer pair will be (2,1). The second player will win by subtracting 1 from 2.
Example case 2. If the first player choose to move (4,5) to (4,1) the second player will make it to (1,1). If the first player choose to move (5,6) to (5,1) the second player will make it to (1,1). So regardless of the move of the first player, the second will always win.
Example case 3. The first player will select pair (3,5) and make it to (3,2). Now both pairs are equal. So whatever the move of second player he will just mirror that move in another pair. This will ensure his win.
Author:  satej 
Tester:  gerald 
Editorial  http://discuss.codechef.com/problems/GAMEAAM 
Tags  cook42, easy, gametheory, satej , spraguegrundy 
Date Added:  15012014 
Time Limit:  0.5 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions