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

Source: codechef | Difficulty: VERY_HARD
Tags: Game theory


Solutions:
import sys
t = int(input())

def g(a, b):
	if a > b:
		tmp = a
		a = b
		b = tmp
	if b == a:
		return 0
	if b % a == 0:
		return int(b / a) - 1
	r = g(b % a, a)
	q = int(b / a)
	if r >= q:
		return q - 1
	else:
		return q

def mex(x):
	n = len(list(x.keys()))
	for i in range(n):
		if i not in x:
			return i
	return i

def g2(a, b):
	if a == b:
		return 0
	if a > b:
		tmp = a
		a = b
		b = tmp
	if b % a == 0:
		return int(b / a) - 1
	q = int(b / a)
	x = {}
	r = b % a
	for i in range(q):
		x[g2(r + i * a, a)] = True
	return mex(x)
while t:
	n = int(input())
	x = 0
	while n:
		line = input().split()
		a = int(line[0])
		b = int(line[1])
		x ^= g(a, b)
		n -= 1
	if x:
		sys.stdout.write('YES\n')
	else:
		sys.stdout.write('NO\n')
	t -= 1


import math
import sys
import string
t = int(input())
while t:
	n = int(input())
	x = 0
	while n:
		(a, b) = [int(x) for x in input().split()]
		y = int(abs(a * a - b * b) / (a * b))
		x = x ^ y
		n -= 1
	print('YES' if x else 'NO')
	t -= 1