Two players are playing a game of Tower Breakers! Player $1$ always moves first, and both players always play optimally.The rules of the game are as follows:   

Initially there are $n$ towers.
Each tower is of height $m$.   
The players move in alternating turns. 
In each turn, a player can choose a tower of height $x$ and reduce its height to $y$, where $1\leq y<x$ and $y$ evenly divides $x$.  
If the current player is unable to make a move, they lose the game.   

Given the values of $n$ and $m$, determine which player will win. If the first player wins, return $1$.  Otherwise, return $2$.  

Example. 
$n=2$ 

$m=6$    

There are $2$ towers, each $6$ units tall.  Player $1$ has a choice of two moves: 

- remove $3$ pieces from a tower to leave $6$ as $6 \quad modulo \quad 3=0$ 

- remove $5$ pieces to leave $1$   

Let Player $1$ remove $3$. Now the towers are $3$ and $6$ units tall.

Player $2$ matches the move. Now the towers are both $3$ units tall. 

Now Player $1$ has only one move. 

Player $1$ removes $2$ pieces leaving $1$.  Towers are $1$ and $2$ units tall. 

Player $2$ matches again.  Towers are both $1$ unit tall.  

Player $1$ has no move and loses. Return $2$.

Function Description  

Complete the towerBreakers function in the editor below.   

towerBreakers has the following paramter(s):  

int n: the number of towers  
int m: the height of each tower  

Returns  

int: the winner of the game   

Input Format

The first line contains a single integer $t$, the number of test cases. 

Each of the next $t$ lines describes a test case in the form of $2$ space-separated integers, $n$ and $m$.  

Constraints

$1\leq t\leq100$
$1\leq n,m\leq10^6$

Sample Input
STDIN   Function
-----   --------
2       t = 2
2 2     n = 2, m = 2
1 4     n = 1, m = 4

Sample Output
2
1

Explanation

We'll refer to player $1$ as $P1$ and player $2$ as $P2$

In the first test case, $P1$ chooses one of the two towers and reduces it to $1$. Then $P2$ reduces the remaining tower to a height of $1$. As both towers now have height $1$, $P1$ cannot make a move so $P2$ is the winner.

In the second test case, there is only one tower of height $4$. $P1$ can reduce it to a height of either $1$ or $2$. $P1$ chooses $1$ as both players always choose optimally. Because $P2$ has no possible move, $P1$ wins.

Difficulty: EASY
Tags: Game theory

Starter code:

Solutions:
test = int(input())
for _ in range(test):
	(n, m) = map(int, input().strip().split())
	if m == 1:
		print(2)
	elif n % 2 == 1:
		print(1)
	else:
		print(2)


for t in range(int(input())):
	(n, m) = [int(x) for x in input().split()]
	if n % 2 == 0:
		print(2)
	elif m == 1:
		print(2)
	else:
		print(1)


for test in range(int(input())):
	(N, M) = map(int, input().split())
	print(2 - (N % 2 and M > 1))


stdin = int(input())
while stdin > 0:
	a = input().split(' ')
	b = int(a[0])
	c = int(a[1])
	if c == 1 and b >= 1:
		print(2)
	elif b == 1 and c > 1:
		print(1)
	elif b % 2 == 0:
		print(2)
	else:
		print(1)
	stdin -= 1


for _ in range(int(input())):
	(N, M) = map(int, input().split())
	if M > 1:
		print(1 if N % 2 == 1 else 2)
	else:
		print(2)


t = int(input().strip())
for each in range(t):
	(n, m) = [int(i) for i in input().strip().split(' ')]
	if n % 2 == 0:
		print(2)
	elif m == 1:
		print(2)
	else:
		print(1)


import sys

def ints():
	return map(int, sys.stdin.readline().split())
[t] = ints()
for i in range(0, t):
	[n, m] = ints()
	if n % 2 == 0 or m == 1:
		print(2)
	else:
		print(1)


t = int(input())
for i in range(t):
	(n, m) = list((int(x) for x in input().split(' ')))
	if m == 1 or n % 2 == 0:
		print('2')
	else:
		print('1')


T = int(input())
while T > 0:
	(N, M) = list(map(int, input().split()))
	if M == 1:
		print('2')
	elif N % 2 == 0:
		print('2')
	else:
		print('1')
	T -= 1


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	if m == 1:
		print(2)
	else:
		print(1 if n % 2 == 1 else 2)


t = int(input())
for e in range(t):
	(n, m) = [int(i) for i in input().strip().split(' ')]
	win = 1
	if m == 1:
		win = 2
	elif n % 2 == 0:
		win = 2
	print(win)


for i in range(int(input())):
	(n, m) = map(int, input().split())
	print((m == 1 or not n % 2) + 1)


cases = int(input())
for i in range(cases):
	d = list(map(int, input().split(' ')))
	N = d[0]
	M = d[1]
	if M == 1 or N % 2 == 0:
		print(2)
	else:
		print(1)


import math
t = int(input().strip())
for i in range(t):
	(a, b) = [int(x) for x in input().strip().split(' ')]
	if b == 1 or a % 2 == 0:
		print(2)
	else:
		print(1)


def isprime(n):
	if n == 2:
		return True
	if n == 3:
		return True
	if n % 2 == 0:
		return False
	if n % 3 == 0:
		return False
	i = 5
	w = 2
	while i * i <= n:
		if n % i == 0:
			return False
		i += w
		w = 6 - w
	return True
T = int(input())
for _ in range(T):
	(n, m) = map(int, input().split())
	if m == 1:
		print(2)
	elif isprime(m):
		if n % 2 == 0:
			print(2)
		else:
			print(1)
	elif n % 2 != 0:
		print(1)
	else:
		print(2)


import sys
t = int(input().strip())
res = 0
for line in sys.stdin:
	res = line.rstrip('\n')
	data = res.split(' ')
	n = int(data[0])
	m = int(data[1])
	if m == 1 or n % 2 == 0:
		print(2)
	else:
		print(1)


for _ in range(int(input())):
	(n, m) = input().split()
	print([1, 2][int(n) % 2 == 0 or int(m) == 1])


t = int(input().strip())
for i in range(t):
	(n, m) = input().strip().split(' ')
	(n, m) = [int(n), int(m)]
	print(2 if (m == 1) | (n % 2 == 0) else 1)


T = int(input())
for i in range(0, T):
	(N, M) = input().split()
	N = int(N)
	M = int(M)
	if M == 1 or N % 2 == 0:
		print(2)
	else:
		print(1)


t = int(input().strip())
for case in range(t):
	data = input().strip().split(' ')
	n = int(data[0])
	m = int(data[1])
	if m == 1:
		print('2')
	elif n % 2 == 1:
		print('1')
	else:
		print('2')


for _ in range(int(input())):
	(N, M) = map(int, input().split())
	if N % 2 == 0:
		print(2)
	elif M > 1:
		print(1)
	else:
		print(2)


lenin = input()

def fun(a):
	if a[1] == 1 or a[0] % 2 == 0:
		print(2)
	else:
		print(1)
for i in range(int(lenin)):
	fun(list(map(int, input().split(' '))))


for test in range(int(input())):
	(n, m) = [int(x) for x in input().split(' ')]
	if m == 1 or n % 2 == 0:
		print('2')
	else:
		print('1')


T = int(input())
for _ in range(T):
	(tnum, theight) = map(int, input().split())
	if theight == 1:
		print(2)
		continue
	elif tnum == 1:
		print(1)
		continue
	elif tnum % 2 == 0:
		print(2)
		continue
	elif tnum % 2 == 1:
		print(1)
		continue


t = int(input())
for i in range(t):
	(n, m) = input().strip().split(' ')
	if m == '1':
		print('2')
	else:
		n = int(n)
		print('2' if n % 2 == 0 else '1')


t = int(input())
(n, m) = (0, 1)
l = []
for _ in range(t):
	l.append(list(map(int, input().split())))
for i in range(t):
	print(2 if l[i][m] == 1 or l[i][n] % 2 == 0 else 1)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	if m == 1 or n % 2 == 0:
		print(2)
	else:
		print(1)


for case in range(int(input())):
	(n, m) = map(int, input().split())
	print(2 if m == 1 or not n % 2 else 1)


testcases = int(input())

def towerbreaker(n, m):
	if m == 1:
		print('2')
		return
	if n % 2 == 1:
		print('1')
	else:
		print('2')
	return
for i in range(0, testcases):
	(n, m) = [int(x) for x in input().split(' ')]
	towerbreaker(n, m)


for _ in range(int(input())):
	(N, M) = map(int, input().split())
	print('1' if N % 2 and M > 1 else '2')


t = int(input())
for i in range(t):
	(n, m) = list(map(int, input().split(' ')))
	print('2' if n % 2 == 0 or m == 1 else '1')


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	if m == 1:
		print(2)
	elif n % 2 == 0:
		print(2)
	else:
		print(1)


t = int(input().strip())
for _ in range(t):
	(n, m) = [int(x) for x in input().split()]
	if n % 2 == 0 or m == 1:
		print(2)
	else:
		print(1)


testCases = int(input())
for x in range(0, testCases):
	(n, m) = (int(x) for x in input().split())
	print('2') if m == 1 or n % 2 == 0 else print('1')


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	print(2 if m == 1 or n % 2 == 0 else 1)


t = int(input())
for i in range(t):
	(n, m) = [int(x) for x in input().split()]
	print(2 if m == 1 or n % 2 == 0 else 1)


for i in range(int(input())):
	(n, m) = [int(i) for i in input().split()]
	if m == 1:
		print(2)
	elif n % 2 == 1:
		print(1)
	else:
		print(2)


t = int(input().strip())
for _ in range(t):
	(n, m) = list(map(int, input().strip().split()))
	if m == 1 or n % 2 == 0:
		print(2)
	else:
		print(1)


for _ in range(int(input())):
	(n, m) = [int(x) for x in input().split(' ')]
	print(int(n % 2 == 0 or m == 1) + 1)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	if m == 1 or n % 2 == 0:
		print(2)
	else:
		print(1)


t = int(input())
for i in range(t):
	(n, m) = input().split(' ')
	(n, m) = [int(n), int(m)]
	if m == 1 or n % 2 == 0:
		print('2')
	else:
		print('1')


for t in range(int(input().strip())):
	(n, m) = [int(a) for a in input().strip().split(' ')]
	if m == 1:
		print(2)
	elif n == 1:
		print(1)
	elif n % 2 == 1:
		print(1)
	elif n % 2 == 0:
		print(2)


t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	if b == 1 or a % 2 == 0:
		print('2')
	else:
		print('1')


print('\n'.join(map(lambda x: '1' if int(x[0]) % 2 and x[1] != '1' else '2', (input().split() for _ in range(int(input()))))))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	if m == 1 or n % 2 == 0:
		print('2')
	else:
		print('1')


def divisors(n):
	if n != 1:
		yield 1
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			yield i
			yield (n // i)
grun = {1: 0}

def grundy(n):
	if n not in grun:
		a = {grundy(i) for i in divisors(n)}
		k = 0
		while k in a:
			k += 1
		grun[n] = k
	return grun[n]
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	print(1 if n & 1 and grundy(m) else 2)


N = int(input())
for test in range(N):
	(n, m) = [int(i) for i in input().split()]
	if n % 2 == 0:
		print(2)
	elif m <= 1:
		print(2)
	else:
		print(1)


import sys
T = int(input())
for x in range(T):
	(n, m) = [int(i) for i in input().split()]
	if m == 1 or n % 2 == 0:
		print(2)
	else:
		print(1)


t = int(input())
for i in range(t):
	(n, k) = input().split(' ')
	n = int(n)
	k = int(k)
	if n % 2 == 0 or k == 1:
		print('2')
	else:
		print('1')


for _ in range(int(input())):
	(n, m) = [int(e) for e in input().split()]
	print('2' if m == 1 or n % 2 == 0 else '1')


tests = int(input())
inputs = []
for i in range(tests):
	arr = [int(arr_temp) for arr_temp in input().strip().split(' ')]
	inputs.append(arr)
for in_put in inputs:
	N = in_put[0]
	M = in_put[1]
	if N % 2 == 0 or M == 1:
		print('2')
	else:
		print('1')


for _ in range(int(input())):
	(n, h) = map(int, input().split())
	r = 1
	if h == 1:
		r = 2
	elif n % 2 == 0:
		r = 2
	print(r)


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	if m == 1 or n % 2 == 0:
		print('2')
	else:
		print('1')


t = int(input())
for i in range(t):
	(n, m) = [int(i) for i in input().split()]
	if m != 1 and n % 2 == 1:
		print(1)
	else:
		print(2)


n_entry = input()
for i in range(int(n_entry)):
	(n, m) = input().split(' ')
	if int(n) % 2 and int(m) > 1:
		print(1)
	else:
		print(2)


T = int(input())
for t in range(T):
	(n, m) = [int(x) for x in input().strip().split()]
	if m == 1:
		print(2)
	elif n % 2 == 1:
		print(1)
	else:
		print(2)


t = int(input())
for i in range(t):
	(n, h) = map(int, input().split())
	if h == 1 or n % 2 == 0:
		res = 2
	else:
		res = 1
	print(res)


T = int(input())
for t in range(T):
	(N, M) = [int(i) for i in input().split()]
	n = N
	m = M
	i = 2
	l = []
	while m > 1:
		if m % i == 0:
			l += [i]
			m /= i
			break
		else:
			i += 1 + (i > 2)
	if n == 1 or (n & 1 and len(l) == 1):
		print('1')
	else:
		print('2')


for _ in range(int(input())):
	(n, m) = input().strip().split(' ')
	(n, m) = (int(n), int(m))
	if m == 1:
		print(2)
	elif n == 1:
		print(1)
	elif n % 2 == 1:
		print(1)
	else:
		print(2)


for _ in range(int(input())):
	(N, M) = [int(i) for i in input().split()]
	print(2 if M == 1 or N % 2 == 0 else 1)


def ans(n, m):
	if m == 1:
		return 2
	if n % 2:
		return 1
	else:
		return 2
t = int(input())
for i in range(t):
	print(ans(*[int(s) for s in input().split()]))


t = int(input())
for i in range(t):
	(n, m) = [int(x) for x in input().split(' ')]
	if n % 2 == 0 or m == 1:
		output = 2
	else:
		output = 1
	print(output)


import sys
t = int(input())
for i in range(0, t):
	(n, m) = map(int, input().split())
	if m == 1 or n % 2 == 0:
		print(2)
	else:
		print(1)


for _ in range(int(input())):
	(n, m) = map(int, input().strip().split(' '))
	if m == 1 or n % 2 == 0:
		print(2)
	else:
		print(1)


t = int(input())
for _ in range(t):
	(n, m) = [int(x) for x in input().split()]
	if m == 1:
		print(2)
		continue
	if n % 2 == 0:
		print(2)
	else:
		print(1)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	print(2 if m == 1 or n % 2 == 0 else 1)


t = int(input())
for _ in range(t):
	(n, m) = [int(x) for x in input().split()]
	print(1 if n & 1 and m != 1 else 2)


t = int(input())
for _ in range(t):
	(n, m) = [int(i) for i in input().split()]
	if m == 1 or n % 2 == 0:
		print('2')
	else:
		print('1')


testcases = int(input())
for x in range(testcases):
	(towers, height) = map(int, input().split())
	if height == 1:
		print(2)
	elif towers % 2 == 0:
		print(2)
	else:
		print(1)


n = int(input())
for _ in range(n):
	(N, M) = input().split(' ')
	(N, M) = (int(N), int(M))
	print(2 if M == 1 or N % 2 == 0 else 1)


def prime(a):
	return not (a < 2 or any((a % x == 0 for x in range(2, int(a ** 0.5) + 1))))
testCase = int(input())
for i in range(testCase):
	(n, m) = [int(s) for s in input().strip().split()]
	if m == 1:
		print(2)
	elif n % 2 == 0:
		print(2)
	else:
		print(1)


def divisorCount(x):
	ans = 0
	for i in range(2, x + 1):
		if x % i == 0:
			x = x // i
			ans += 1
		else:
			i += 1
			if i > x:
				break
	return int(ans)
for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	m = divisorCount(m)
	ans = 0
	for x in range(n):
		ans = ans ^ m
	print(2 if ans == 0 else 1)


def winner(n, m):
	if m == 1 or n % 2 == 0:
		return 2
	else:
		return 1
num_tests = int(input().strip())
for i in range(num_tests):
	[n, m] = list(map(int, input().strip().split(' ')))
	print(winner(n, m))


n = int(input())
for i in range(n):
	l = list(map(int, input().split()))
	if l[1] == 1 or l[0] % 2 == 0:
		print(2)
	else:
		print(1)


import functools

def factors(n):
	return set(functools.reduce(list.__add__, ([i, n // i] for i in range(2, int(n ** 0.5) + 1) if n % i == 0)))

def prime_factors(n):
	i = 2
	factors = []
	while i * i <= n:
		if n % i:
			i += 1
		else:
			n //= i
			factors.append(i)
	if n > 1:
		factors.append(n)
	return factors
t = int(input())
for T in range(t):
	(n, m) = map(int, input().split())
	if m == 1 or n % 2 == 0:
		print(2)
	else:
		print(1)


T = int(input())
while T > 0:
	T -= 1
	(n, m) = tuple(map(int, input().split(' ')))
	if m == 1:
		print('2')
	elif n % 2:
		print('1')
	else:
		print('2')


for _ in range(int(input())):
	(N, M) = map(int, input().split())
	p1 = N % 2 == 1 and M > 1
	print(1 if p1 else 2)


quantity = int(input())
for i in range(quantity):
	(n, m) = map(int, input().split())
	print(2 if m == 1 or n % 2 == 0 else 1)


q = int(input())
for _ in range(q):
	(n, m) = input().strip().split(' ')
	(n, m) = [int(n), int(m)]
	if n % 2 == 0 or (n % 2 != 0 and m == 1):
		print('2')
	else:
		print('1')


def prod(iterable):
	p = 1
	for n in iterable:
		p *= n
	return p
for i in range(int(input())):
	l = list(map(int, input().split(' ')))
	x = l[0]
	y = l[1]
	print('2' if x % 2 == 0 or y == 1 else '1')


import sys
for _ in range(int(input())):
	(n, m) = input().strip().split(' ')
	(n, m) = [int(n), int(m)]
	if m == 1 or n % 2 == 0:
		print(2)
	else:
		print(1)


T = int(input().strip())
for t in range(T):
	(N, M) = input().split()
	(N, M) = (int(N), int(M))
	if M == 1:
		print(2)
	elif N % 2 == 0:
		print(2)
	else:
		print(1)


def winner(n, m):
	return 2 if m == 1 or n % 2 == 0 else 1
t = int(input())
for _ in range(t):
	(n, m) = [int(el) for el in input().split()]
	print(winner(n, m))


for t in range(int(input())):
	n = input().split()
	if n[1] == '1' or int(n[0]) % 2 == 0:
		print(2)
	else:
		print(1)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	print(2 if m == 1 or n % 2 == 0 else 1)


for _ in range(int(input())):
	(N, M) = tuple([int(x) for x in input().split(' ')])
	if M == 1 or N % 2 == 0:
		print(2)
	else:
		print(1)


def factor(n):
	l = []
	up = int(n ** 0.5) + 1
	for x in range(1, up):
		if n % x == 0:
			l.append(x)
			n = n / x
	return l
t = int(input())
for _ in range(t):
	l = list(map(int, input().split()))
	if l[1] == 1 or l[0] % 2 == 0:
		print(2)
	else:
		print(1)


import sys
t = int(input())
for tt in range(t):
	(n, m) = [int(i) for i in input().split()]
	if m == 1:
		print(2)
	elif n % 2 == 0:
		print(2)
	else:
		print(1)


numcases = int(input())
for case in range(numcases):
	(N, M) = [int(x) for x in input().split()]
	if M != 1 and N % 2 != 0:
		print('1')
	else:
		print('2')


T = int(input())
for __ in range(T):
	(N, M) = map(int, input().split())
	print(2 if M == 1 or N % 2 == 0 else 1)


t = int(input())
for _ in range(t):
	(n, m) = (int(i) for i in input().split())
	if n % 2 == 0 or m == 1:
		print(2)
	else:
		print(1)


for i in range(int(input())):
	[n, m] = list(map(int, input().strip().split()))
	if m == 1:
		print(2)
		continue
	elif n % 2 == 0:
		print(2)
	else:
		print(1)


tests = int(input())
for i in range(tests):
	(n, m) = [int(x) for x in input().split(' ')]
	if m == 1 or n % 2 == 0:
		print(2)
	else:
		print(1)


num_test_cases = int(input())
for i in range(num_test_cases):
	(n, m) = [int(val) for val in input().split()]
	if m == 1 or n % 2 == 0:
		print('2')
	else:
		print('1')


t = int(input())
for x in range(t):
	[n, m] = [int(y) for y in input().strip().split(' ')]
	if m == 1:
		print(2)
	elif n % 2 == 0:
		print(2)
	else:
		print(1)


T = int(input().strip())
for t in range(T):
	(N, M) = [int(tmp) for tmp in input().strip().split(' ')]
	if M == 1:
		print(2)
	else:
		print(2 - N % 2)


t = int(input())
for _ in range(t):
	(N, M) = map(int, input().split())
	if N % 2 == 0 or M == 1:
		print('2')
	else:
		print('1')


t = int(input().strip())
for t0 in range(t):
	(n, m) = list(map(int, input().strip().split(' ')))
	if n % 2 == 0 or m == 1:
		print(2)
	else:
		print(1)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	print(2 if m == 1 or n % 2 == 0 else 1)