Two players (numbered $\mbox{1}$ and $2$) are playing a game of Tower Breakers! The rules of the game are as follows:

Player $\mbox{1}$ always moves first.
Initially there are $N$ towers of various heights.
The players move in alternating turns. In each turn, a player must choose a tower of height $\mbox{X}$ and break it down into $\mathbf{Y}$ towers, each of height $\mbox{z}$. The numbers $\mathbf{Y}$ and $\mbox{z}$ must satisfy $Y\times Z=X$ and $Y>1$.  
If the current player is unable to make any move, they lose the game.

Given the value of $N$ and the respective height values for all towers, can you determine who will win, assuming both players always move optimally? If the first player wins, print $\mbox{1}$; otherwise, print $2$.

Input Format

The first line contains an integer, $\mathbf{T}$, denoting the number of test cases. 

The $2T$ subsequent lines define the test cases. Each test case is described by two lines:

An integer, $N$, denoting the number of towers.
$N$ space-separated integers, $h_0,h_1,\ldots,h_{N-1}$, where each $h_i$ describes the height of tower $\boldsymbol{i}$.

Constraints

$1\leq T\leq200$
$1\leq N\leq100$
$1\leq h_i\leq10^5$

Output Format

For each test case, print a single integer denoting the winner (i.e., either $\mbox{1}$ or $2$) on a new line.

Sample Input
2
2 
1 2
3 
1 2 3

Sample Output
1
2

Explanation

In the first test case, the first player simply breaks down the second tower of height $2$ into two towers of height $\mbox{1}$ and wins.

In the second test case, there are only two possible moves:

Break the second tower into $2$ towers of height $\mbox{1}$.
Break the third tower into $3$ towers of height $\mbox{1}$. 

Whichever move player $\mbox{1}$ makes, player $2$ can make the other move and win the game.

Difficulty: MEDIUM
Tags: Game theory

Starter code:

Solutions:
from functools import reduce

def mex(s):
	f = 0
	m = max(s)
	for i in range(m):
		if i not in s:
			return i
	return m + 1

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

def grundy(n):
	if n in [0, 1]:
		return 0
	s = {0}
	f = factors(n) - {1, n}
	for e in f:
		if e % 2 == 1:
			s.add(grundy(int(n / e)))
	return mex(s)
t = int(input().strip())
for each in range(t):
	n = int(input().strip())
	arr = [int(i) for i in input().strip().split(' ')]
	g = grundy(arr[0])
	for i in range(1, n):
		g ^= grundy(arr[i])
	if g == 0:
		print('2')
	else:
		print('1')


g = [0]
for N in range(1, 10 ** 5 + 1):
	i = N
	twos = 0
	c = 0
	while N % 2 == 0:
		N //= 2
		twos = 1
	d = 3
	while d * d <= N:
		while N % d == 0:
			c += 1
			N //= d
		d += 2
	if N > 1:
		c += 1
	g.append(c + twos)
for _ in range(int(input())):
	input()
	r = 0
	for h in map(int, input().split()):
		r ^= g[h]
	print(1 if r else 2)


from functools import reduce
from bisect import insort

def getFactors(n):
	i = int(n ** 0.5)
	while i > 1:
		if n % i == 0:
			yield i
		i -= 1

def grundy(n):
	if n == 1:
		return 0
	if grundy_nums[n]:
		return grundy_nums[n]
	s = [0]
	for k in getFactors(n):
		if k % 2:
			insort(s, grundy(n // k))
		if n // k % 2:
			insort(s, grundy(k))
	(i, mex) = (0, 0)
	while i < len(s):
		if mex == s[i]:
			mex += 1
		elif mex < s[i]:
			break
		i += 1
	grundy_nums[n] = mex
	return mex
n = 100000
grundy_nums = [0] * (n + 1)
for _ in range(int(input())):
	_ = input()
	h = (grundy(int(x)) for x in input().split(' '))
	print(1 if reduce(lambda x, y: x ^ y, h) else 2)


import math

def find(v):
	for i in range(1, len(v)):
		if v[i] - v[i - 1] > 1:
			return v[i - 1] + 1
	return v[len(v) - 1] + 1
g = [0] * 100003
for i in range(2, 100001):
	p = int(math.sqrt(i))
	v = []
	for j in range(1, p + 1):
		if i % j == 0:
			if j % 2:
				v.append(g[i // j])
			if i // j % 2:
				v.append(g[j])
	v.sort()
	g[i] = v[0] - 1 if v[0] > 0 else find(v)
t = int(input())
for _ in range(t):
	n = int(input())
	h = [int(x) for x in input().split()]
	r = 0
	for i in range(n):
		r = r ^ g[h[i]]
	if r:
		print(1)
	else:
		print(2)


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) if n // i & 1 else 0 for i in divisors(n)}
		k = 0
		while k in a:
			k += 1
		grun[n] = k
	return grun[n]
for _ in range(int(input())):
	input()
	x = 0
	for i in map(int, input().split()):
		x ^= grundy(i)
	print(1 if x else 2)


from sys import stdin

def read_ints():
	return [int(a.strip()) for a in stdin.readline().strip().split(' ')]

def nimber(num):
	min_d = 3
	ret = 0
	if num % 2 == 0:
		ret += 1
		while num % 2 == 0:
			num /= 2
	while min_d * min_d <= num:
		while num % min_d == 0:
			num /= min_d
			ret += 1
		min_d += 1
	if num > 1:
		ret += 1
	return ret
for _ in range(read_ints()[0]):
	(n,) = read_ints()
	result = 0
	for a in read_ints():
		result ^= nimber(a)
	print(1 if result else 2)


import math
from operator import xor
from functools import reduce

def primes_upto(n):
	sieve = [True] * n
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		if sieve[i]:
			sieve[i * i::i + i] = [False] * ((n - i * i - 1) // (i + i) + 1)
	return [2] + list((i for i in range(3, n, 2) if sieve[i]))
primes = primes_upto(100000)
factors_memo = {1: 0}

def n_prime_factors(n):
	if n not in factors_memo:
		p = next((p for p in primes if n % p == 0))
		factors_memo[n] = 1 + n_prime_factors(n // p)
	return factors_memo[n]

def g_number(n):
	g = n_prime_factors(n)
	if n % 2 == 0:
		n //= 2
		while n % 2 == 0:
			n //= 2
			g -= 1
	return g
for _ in range(int(input().strip())):
	input()
	heights = list(map(int, input().strip().split(' ')))
	print('1' if reduce(xor, map(g_number, heights), 0) else '2')


from functools import reduce

def even_power(n):
	count = 0
	while n % 2 == 0:
		count += 1
		n //= 2
	return count

def odd_primes(n):
	primefac = []
	while n % 2 == 0:
		n //= 2
	d = 3
	while d * d <= n:
		while n % d == 0:
			primefac.append(d)
			n //= d
		d += 2
	if n > 1:
		primefac.append(n)
	return primefac
t = int(input())
for i in range(t):
	n = int(input())
	l = [int(i) for i in input().split()]
	l2 = [len(odd_primes(i)) if i % 2 == 1 else len(odd_primes(i)) + 1 for i in l]
	temp = reduce(lambda x, y: x ^ y, l2)
	if temp == 0:
		print(2)
	else:
		print(1)


def factorTD(x):
	if x <= 1:
		return []
	f = []
	e = 0
	while x % 2 == 0:
		x //= 2
		e += 1
	if e > 0:
		f.append((2, e))
	p = 3
	while p * p <= x:
		e = 0
		while x % p == 0:
			x //= p
			e += 1
		if e > 0:
			f.append((p, e))
		p += 2
	if x > 1:
		f.append((x, 1))
	return sorted(f)

def divisors(n):
	div = [1]
	for (p, r) in factorTD(n):
		div = [d * p ** e for d in div for e in range(r + 1)]
	return sorted(div)

def mex(S):
	i = 0
	while i in S:
		i += 1
	return i

def sg_tower_breakers(X, cache={}):
	key = X
	S = set()
	if X == 1:
		return 0
	if key in cache:
		return cache[key]
	for Y in divisors(X):
		if Y > 1:
			Z = X / Y
			s = 0
			if Y % 2 == 1:
				s ^= sg_tower_breakers(Z)
			S.add(s)
	cache[key] = mex(S)
	return cache[key]
for T in range(int(input())):
	N = int(input())
	heights = list(map(int, input().split()))
	nim_sum = 0
	for h in heights:
		nim_sum ^= sg_tower_breakers(h)
	print([2, 1][nim_sum > 0])


from operator import xor
from functools import reduce
ar = tuple(((input(), tuple(map(int, input().split())))[1] for _ in range(int(input()))))
n = max(map(max, ar)) + 1
sieve = [0] * n
for i in range(2, n):
	if not sieve[i]:
		sieve[i] = i
		for j in range(i * i, n, i):
			if not sieve[j]:
				sieve[j] = i

def factors(x):
	res = not x & 1
	while sieve[x]:
		if sieve[x] & 1:
			res += 1
		x //= sieve[x]
	return res
print(*(1 if reduce(xor, map(factors, row), 0) else 2 for row in ar), sep='\n')


nMax = int(100000.0)
A = [True for m in range(nMax + 1)]
A[0] = False
A[1] = False
for i1 in range(2, int(nMax ** 0.5 // 1) + 1):
	if A[i1]:
		Mult = 2
		while Mult * i1 <= nMax:
			A[Mult * i1] = False
			Mult += 1
PrimeSet = [m for m in range(nMax + 1) if A[m]]

def GetFactors(n):
	Out = []
	for i1 in PrimeSet:
		while n % i1 == 0:
			Out.append(i1)
			n /= i1
		if i1 > n:
			break
	return Out

def GetG(n):
	if n == 2:
		return 1
	if n == 1:
		return 0
	Factors = GetFactors(n)
	if Factors[0] == 2:
		return len(Factors) - Factors.count(2) + 1
	return len(Factors)
T = int(input())
for i1 in range(T):
	input()
	Arr = [GetG(int(m)) for m in input().strip().split()]
	S = 0
	for i2 in Arr:
		S ^= i2
	if S != 0:
		P = 1
	else:
		P = 2
	print(P)


def odd_primes(n):
	primfac = []
	d = 2
	while d * d <= n:
		while n % d == 0:
			if d % 2 == 1:
				primfac.append(d)
			n //= d
		d += 1
	if n > 1:
		if n % 2 == 1:
			primfac.append(n)
	return len(primfac)
T = int(input())
for _ in range(T):
	N = int(input())
	a = [int(x) for x in input().strip().split(' ')]
	if a[0] % 2 == 0:
		total = odd_primes(a[0]) + 1
	else:
		total = odd_primes(a[0])
	for i in range(1, N):
		if a[i] % 2 == 0:
			total = total ^ odd_primes(a[i]) + 1
		else:
			total = total ^ odd_primes(a[i])
	if total == 0:
		print(2)
	else:
		print(1)


def gen_primes(n):
	sieve = [True] * n
	for i in range(3, int(n ** 0.5) + 1, 2):
		if sieve[i]:
			sieve[i * i::2 * i] = [False] * ((n - i * i - 1) // (2 * i) + 1)
	return [2] + [i for i in range(3, n, 2) if sieve[i]]
primes = gen_primes(int(100000.0))

def factorize(n):
	factors = []
	for p in primes:
		if p * p > n:
			break
		i = 0
		while n % p == 0:
			n //= p
			i += 1
		if i > 0:
			factors.append((p, i))
	if n > 1:
		factors.append((n, 1))
	return factors
div_memo = dict()

def divisors(n):
	if n not in div_memo:
		factors = factorize(n)
		div = [1]
		for (p, r) in factors:
			div = [d * p ** e for d in div for e in range(r + 1)]
		div_memo[n] = list(filter(lambda x: x < n, div))
	return div_memo[n]

def mex(values):
	max_val = max(values)
	return min(frozenset(range(max_val + 3)).difference(values))
grundy_memo = {1: 0, 2: 1}

def grundy(n):
	if n not in grundy_memo:
		grundy_memo[n] = mex([grundy(div) if n // div % 2 == 1 else 0 for div in divisors(n)])
	return grundy_memo[n]
t = int(input())
for _ in range(t):
	n = int(input())
	towers = list(map(int, input().split()))
	result = 0
	for tower in towers:
		result ^= grundy(tower)
	print(1 if result != 0 else 2)


MAXX = 10 ** 5
sieve = set()
odd_primes = []
p = 1
while True:
	p += 2
	if p > MAXX:
		break
	if p not in sieve:
		odd_primes.append(p)
		sieve.update((p * x for x in range(p, MAXX // p + 1, 2)))
cache = {1: 0, 2: 1}
cache.update({p: 1 for p in odd_primes})
for elem in range(4, MAXX + 1):
	if elem in cache:
		continue
	if elem % 2 == 0:
		if elem % 4 == 0:
			cache[elem] = cache[elem // 2]
		else:
			cache[elem] = 1 + cache[elem // 2]
	else:
		for prime in odd_primes:
			if elem % prime == 0:
				cache[elem] = 1 + cache[elem // prime]
				break
from functools import reduce
for _ in range(int(input())):
	n = int(input())
	towers = list(map(lambda x: cache[int(x)], input().strip().split(' ')))
	xor = reduce(lambda x, y: x ^ y, towers)
	if xor == 0:
		print(2)
	else:
		print(1)


from functools import reduce

def numprimefactors(x):
	ans = 0
	if x % 2 == 0:
		ans = 1
		while x % 2 == 0:
			x //= 2
	d = 3
	while d * d <= x:
		while x % d == 0:
			ans += 1
			x //= d
		d += 1
	if x > 1:
		ans += 1
	return ans
T = int(input().strip())
for i in range(T):
	n = int(input().strip())
	arr = [numprimefactors(int(arr_temp)) for arr_temp in input().strip().split(' ')]
	nimsum = reduce(lambda x, y: x ^ y, arr)
	if nimsum:
		print('1')
	else:
		print('2')


N = 100001
f = []
sg = [0] * N
for i in range(N):
	f.append([False] * 50)
m = 0
for i in range(1, N):
	for j in range(0, 50):
		if not f[i][j]:
			break
	sg[i] = j
	m = max(m, j)
	for k in range(i + i, N, i):
		if k // i % 2 == 1:
			f[k][j] = True
		else:
			f[k][0] = True
for _ in range(int(input().strip())):
	n = int(input().strip())
	a = list(map(int, input().strip().split()))
	s = 0
	for i in a:
		s ^= sg[i]
	if s > 0:
		print('1')
	else:
		print('2')


def primosImpares(num):
	count = 0
	if num % 2 == 0:
		count += 1
	while num % 2 == 0:
		num /= 2
	i = 3
	while i * i <= num:
		while num % i == 0:
			num /= i
			if i % 2 != 0:
				count += 1
		i += 1
	if num > 2:
		count += 1
	return count
casos = int(input().strip())
torres = []
for i in range(casos):
	input()
	li = [int(j) for j in input().strip().split(' ')]
	torres.append(li)
for t in torres:
	g = 0
	for e in t:
		p = primosImpares(e)
		g ^= p
	if g == 0:
		print(2)
	else:
		print(1)


def get_primes(n):
	if n < 6:
		return [False, False, True, True, False, True]
	al = [False] + [True] * n
	al[1] = False
	al[2] = True
	ind = 3
	while ind < n + 1:
		if al[ind]:
			for i in range(ind * 2, n + 1, ind):
				al[i] = False
		ind += 2
	return al

def prime_factors(n, primes):
	for i in range(2, n + 1):
		if primes[i] and n % i == 0:
			return [i] + prime_factors(n // i, primes)
	return []
primes = get_primes(100000)

def pile_size(n):
	if n == 1:
		return 0
	if n % 2 == 0:
		add = 1
	else:
		add = 0
	factors = prime_factors(n, primes)
	while 2 in factors:
		factors.pop(0)
	return len(factors) + add
T = int(input())
for i in range(T):
	N = int(input())
	piles = [pile_size(int(k)) for k in input().split()]
	result = 0
	for i in piles:
		result = result ^ i
	if result == 0:
		print('2')
	else:
		print('1')


from functools import lru_cache, reduce
from operator import mul, xor
from collections import Counter
from itertools import product
SIZE = 100000

def sieve(n):
	l = [True] * (n + 1)
	for i in range(2, n + 1):
		if l[i]:
			for j in range(i * i, n + 1, i):
				l[j] = False
	return [x for x in range(2, n + 1) if l[x]]

@lru_cache(None)
def prime_factors(n):
	factors = Counter()
	for p in PRIMES:
		if p > n:
			break
		while n % p == 0:
			factors[p] += 1
			n = n // p
	if n != 1:
		factors[n] += 1
	return factors

@lru_cache(None)
def all_factors(n):
	primes = prime_factors(n).items()
	gen = ([int(p ** i) for i in range(c + 1)] for (p, c) in primes)
	return (x for x in (reduce(mul, p) for p in product(*gen)) if x != 1)

def mex(s):
	for i in range(len(s) + 1):
		if i not in s:
			return i

@lru_cache(None)
def grundy(n):
	if n == 1:
		return 0
	return mex({grundy(n // f) if f != n and f % 2 else 0 for f in all_factors(n)})
PRIMES = sieve(SIZE)
for _ in range(int(input())):
	input()
	nums = [int(x) for x in input().split()]
	print(1 if reduce(xor, (grundy(x) for x in nums)) else 2)


import math

def primes(p):
	count = 0
	if p % 2 == 0:
		count = count + 1
	while p % 2 == 0:
		p = p / 2
	n = p
	for i in range(3, int(math.sqrt(p) + 1), 2):
		while n % i == 0:
			count = count + 1
			n = n / i
	if n > 2:
		count = count + 1
	return count
t = int(input())
for ti in range(t):
	n = int(input())
	a = [int(ai) for ai in input().strip().split(' ')]
	x = 0
	for i in range(0, n):
		x = x ^ primes(a[i])
	if x == 0:
		print('2')
	else:
		print('1')


G = [1] * (10 ** 6 + 1)
G[0] = G[1] = 0
for h in range(2, len(G)):
	g = G[h] + 1
	for m in range(h * 3, len(G), 2 * h):
		G[m] = g

def solve(H):
	s = 0
	for h in H:
		s ^= G[h]
	return s > 0
T = int(input())
for _ in range(T):
	N = int(input())
	H = list(map(int, input().split()))
	print(1 if solve(H) else 2)


pdict = {1: 0}

def primesin(n):
	if n in pdict:
		return pdict[n]
	m = n
	i = 3
	primes = 0
	history = [n]
	if m % 2 == 0:
		primes += 1
		while m % 2 == 0:
			m //= 2
		history.append(m)
	while i <= m ** (1 / 2):
		while m % i == 0:
			m //= i
			history.append(m)
			primes += 1
		if m in pdict:
			p = pdict[m]
			for k in range(len(history)):
				pdict[history[k]] = p + primes - k
			return pdict[n]
		i += 1
	if m > 1:
		primes += 1
	for k in range(len(history)):
		pdict[history[k]] = primes - k
	return pdict[n]
T = int(input())
for _ in range(T):
	input()
	total = 0
	for num in input().split():
		total ^= primesin(int(num))
	if total == 0:
		print(2)
	else:
		print(1)


def primes(n):
	sieve = [True] * n
	for i in range(3, int(n ** 0.5) + 1, 2):
		if sieve[i]:
			sieve[i * i::2 * i] = [False] * int((n - i * i - 1) / (2 * i) + 1)
	return [2] + [i for i in range(3, n, 2) if sieve[i]]

def pfactor_counter(n):
	if n == 1:
		return 0
	n2 = n // 2 + 1
	for p in primes:
		if p <= n2:
			(d, m) = divmod(n, p)
			if m == 0:
				if d > 1:
					return 1 + pfactor_counter(d)
				else:
					return 1
		else:
			if n > primes[-1]:
				primes.append(n)
			return 1

def nim_game(s):
	score = s[0]
	if len(s) > 1:
		for stemp in s[1:]:
			score ^= stemp
	if score == 0:
		return 2
	else:
		return 1
primes = primes(100000)
q = int(input().strip())
for i in range(q):
	n = int(input().strip())
	towers = [int(temp) for temp in input().strip().split(' ')]
	s = []
	for t in towers:
		if t % 2 != 0:
			s.append(pfactor_counter(t))
		else:
			while t % 2 == 0:
				t //= 2
			s.append(pfactor_counter(t) + 1)
	print(nim_game(s))


import math

class Calculator:

	def __init__(self):
		self.alreadyFound = dict()

	def findOddPrimeCount(self, n):
		if n in self.alreadyFound:
			return self.alreadyFound[n]
		result = 1
		if n == 1:
			self.alreadyFound[1] = 0
			return 0
		lim = math.floor(math.sqrt(n))
		if n % 2 == 0:
			return self.findOddPrimeCount(n / 2)
		for i in range(3, lim + 1, 2):
			if n % i == 0:
				result = self.findOddPrimeCount(n / i) + 1
				break
		self.alreadyFound[n] = result
		return result

	def findGrundyNum(self, n):
		if n == 1:
			return 0
		if n % 2 == 0:
			result = self.findOddPrimeCount(n) + 1
		else:
			result = self.findOddPrimeCount(n)
		return result
T = int(input().strip())
calc = Calculator()
for i in range(T):
	N = int(input().strip())
	res = 0
	array = [int(x) for x in input().split()]
	for k in array:
		a = calc.findGrundyNum(k)
		res ^= a
	if res == 0:
		print('2')
	else:
		print('1')


from math import sqrt
from functools import reduce
_primes = [2]

def primes(m):
	for p in _primes:
		if p <= m:
			yield p
		else:
			return
	while p < m:
		p += 1
		for i in primes(sqrt(p)):
			if p % i == 0:
				break
		else:
			_primes.append(p)
			yield p

def prime_size(x):
	s = 0
	while x % 2 == 0:
		s = 1
		x //= 2
	for p in primes(sqrt(x)):
		while x % p == 0:
			s += 1
			x //= p
	return s if x == 1 else s + 1

def solve(towers):
	towers = [prime_size(x) for x in towers]
	if reduce(lambda x, y: x ^ y, towers, 0) == 0:
		return 2
	else:
		return 1
t = int(input())
for _ in range(t):
	n = int(input())
	towers = [int(x) for x in input().split()]
	print(solve(towers))


import functools, operator
LIMIT = 10 ** 5
TOWER_VALUE = [0] * (LIMIT + 1)
TOWER_VALUE[0] = TOWER_VALUE[1] = 0
for i in range(2, LIMIT + 1, 2):
	TOWER_VALUE[i] += 1
for i in range(3, LIMIT + 1, 2):
	if TOWER_VALUE[i] > 0:
		continue
	prime = shift = i
	while shift <= LIMIT:
		for j in range(shift, LIMIT + 1, shift):
			TOWER_VALUE[j] += 1
		shift *= prime

def tower_value(x):
	return TOWER_VALUE[x]

def nims_game(iterable):
	return functools.reduce(operator.xor, iterable) > 0
output_buffer = []
test_count = int(input())
for _ in range(test_count):
	tower_count = int(input())
	tower_sizes = list(map(int, input().split()))
	winnable = nims_game(map(tower_value, tower_sizes))
	output_buffer.append('1' if winnable else '2')
print(*output_buffer, sep='\n')


import sys
games = int(input().strip())

def primes(n):
	n += 1
	nums = [x for x in range(n)]
	for i in range(2, n):
		if nums[i] > 0:
			x = nums[i] * nums[i]
			while x < n:
				nums[x] = 0
				x += nums[i]
	return [num for num in nums if num > 0]
primes = primes(100001)

def reduceToNip(arr, n):
	reducedArr = []
	for i in range(n):
		if arr[i] % 2 == 0:
			oddCount = 1
			while arr[i] % 2 == 0:
				arr[i] //= 2
		else:
			oddCount = 0
		primeInd = 1
		while arr[i] > 1:
			while arr[i] % primes[primeInd] == 0:
				oddCount += 1
				arr[i] //= primes[primeInd]
			primeInd += 1
		reducedArr.append(oddCount)
	return reducedArr

def calcNip(arr, n):
	x = 0
	for el in arr:
		x ^= el
	return 1 if x > 0 else 2
for _ in range(games):
	n = int(input().strip())
	arr = [int(x) for x in input().strip().split()]
	reducedArr = reduceToNip(arr, n)
	print(calcNip(reducedArr, n))


T = int(input().strip())

def primes(n):
	sieve = [True] * n
	sieve[0] = False
	sieve[1] = False
	for i in range(2, int(n ** 0.5) + 1):
		if sieve[i]:
			for j in range(i * i, n, i):
				sieve[j] = False
	return [i for i in range(n) if sieve[i]]

def specialPrimeDivisors(n, primeList):
	backup = n
	if n == 1:
		return 0
	count = 0
	if n % 2 == 0:
		n = n / 2
		count += 1
	while n % 2 == 0:
		n = n / 2
	for prime in primeList:
		while n % prime == 0:
			n = n / prime
			count += 1
	return count
p = primes(100000)
for g in range(T):
	N = int(input().strip())
	towers = list(map(int, input().strip().split(' ')))
	a = 0
	for t in towers:
		a = a ^ specialPrimeDivisors(t, p)
	if a == 0:
		print(2)
	else:
		print(1)


primes = []
for n in range(2, 1001):
	is_prime = True
	for j in primes:
		if n % j == 0:
			is_prime = False
			break
	primes.append(n) if is_prime else next

def find_primes(n):
	if n == 1:
		return 0
	for p in primes:
		if n % p == 0:
			return 1 + find_primes(n / p)
	return 1

def find_odd_primes(n):
	if n == 1:
		return 0
	for p in primes:
		if n % p == 0:
			return p % 2 + find_odd_primes(n / p)
	return 1

def find_grundy(n):
	k = find_odd_primes(n)
	return k + (n + 1) % 2
for i in range(int(input())):
	g = 0
	input()
	for j in map(int, input().split()):
		g ^= find_grundy(j)
	print([1, 2][g == 0])


import math

def count_prime_factors(n):
	c = 0
	if n % 2 == 0:
		c += 1
	while n % 2 == 0:
		n //= 2
	for j in range(3, int(math.sqrt(n)) + 1, 2):
		while n % j == 0:
			n //= j
			c += 1
	if n > 2:
		c += 1
	return c
t = int(input())
while t > 0:
	n = int(input())
	ans = 0
	l = [int(x) for x in input().split()]
	for item in l:
		r = count_prime_factors(item)
		ans ^= r
	if ans:
		print('1')
	else:
		print('2')
	t -= 1


import itertools
flatten_iter = itertools.chain.from_iterable

def factors(n):
	return set(flatten_iter(((i, n // i) for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))
g = {0: 0, 1: 0}
for i in range(2, 100001):
	s = set()
	f = sorted(list(factors(i)))
	for j in range(1, len(f)):
		if f[j] % 2 != 0:
			s.add(g[f[-j - 1]])
		else:
			s.add(0)
	gr = 0
	while gr in s:
		gr += 1
	g[i] = gr
t = int(input())
for ti in range(t):
	n = int(input())
	h = [int(s) for s in input().split()]
	gr1 = 0
	for i in h:
		gr1 ^= g[i]
	if gr1 == 0:
		print(2)
	else:
		print(1)


from collections import defaultdict
from math import sqrt
from functools import lru_cache

def merge(a, b):
	if a & 1:
		return grundy(b)
	return 0

@lru_cache(10 ** 6)
def grundy(n):
	s = set()
	for i in range(1, min(int(sqrt(n)) + 1, n)):
		if n % i:
			continue
		if i > 1:
			s.add(merge(i, n // i))
		s.add(merge(n // i, i))
	ans = 0
	while ans in s:
		ans += 1
	return ans

def solve(N, h_list):
	ans = 0
	for h in h_list:
		ans ^= grundy(h)
	return '1' if ans else '2'

def main():
	T = int(input())
	for _ in range(T):
		N = int(input())
		h_list = list(map(int, input().split()))
		print(solve(N, h_list))
main()


import sys

def sieve(size):
	a = [False, True] * (size // 2 + 2)
	a[:3] = [False, False, True]
	for i in range(2, size + 1):
		if not a[i]:
			continue
		for j in range(i + i, size + 1, i):
			a[j] = False
	return a

def countOddPrimeFactors(n, a):
	while n % 2 == 0:
		n = n // 2
	if n == 1:
		return 0
	if a[n]:
		return 1
	for i in range(2, n):
		if not a[i]:
			continue
		if n % i != 0:
			continue
		c = countOddPrimeFactors(n // i, a) + (0 if i % 2 == 0 else 1)
		return c

def countPrimeFactors(n, a):
	if n == 1:
		return 0
	if a[n]:
		return 1
	for i in range(2, n):
		if n % i == 0 and a[i]:
			return 1 + countPrimeFactors(n // i, a)
b = sieve(100000)
n = int(input().strip())
for i in range(n):
	m = int(input().strip())
	a = [int(x) for x in input().strip().split()]
	x = 0
	for j in a:
		c = countOddPrimeFactors(j, b)
		x ^= c + 1 if j % 2 == 0 else c
	print(2 if x == 0 else 1)


def parseInput(f):
	return [f(x) for x in input().split()]
import math

def grundy(n):
	count = 0
	if n % 2 == 0:
		count += 1
	while n % 2 == 0:
		n //= 2
	i = 3
	while i * i <= n:
		while n % i == 0:
			n //= i
			if i % 2 != 0:
				count += 1
		i += 1
	if n > 2:
		count += 1
	return count
t = int(input())
for _ in range(t):
	n = int(input())
	arr = parseInput(int)
	answer = 0
	for x in arr:
		answer ^= grundy(x)
	print(1 if answer else 2)


from functools import reduce
from math import sqrt

def countOddPrimeFactor(num):
	count = 0
	if num % 2 == 0:
		count += 1
	while num % 2 == 0:
		num /= 2
	for i in range(3, int(sqrt(num)) + 1):
		while num % i == 0:
			num /= i
			if i % 2 != 0:
				count += 1
	if num > 2:
		count += 1
	return count
T = int(input())
while T > 0:
	N = int(input())
	H = list(map(int, input().split(' ')))
	nim = 0
	for h in H:
		nim ^= countOddPrimeFactor(h)
	if nim == 0:
		print(2)
	else:
		print(1)
	T -= 1


def options(n):
	c = 0
	if n % 2 == 0:
		c += 1
	while n % 2 == 0:
		n //= 2
	i = 3
	while i * i <= n:
		while n % i == 0:
			n //= i
			c += 1
		i += 2
	if n > 2:
		c += 1
	return c
t = int(input())
for _ in range(t):
	n = int(input())
	A = list(map(int, input().split()))
	B = [options(a) for a in A]
	nim_sum = 0
	for b in B:
		nim_sum ^= b
	print(1) if nim_sum else print(2)


import bisect
import functools

def builderPrime(n):
	(i, pc, fs, sqn, rs) = (2, 0, [True] * (n + 1), int(pow(n, 0.5) + 1e-05), [None] * (n // 10 + 1000))
	(fs[0], fs[1]) = (False, False)
	base = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
	for x in base:
		rs[pc] = x
		pc += 1
		for y in range(x * x, n + 1, x):
			fs[y] = False
	i = 101
	while i < sqn:
		if fs[i]:
			rs[pc] = i
			pc += 1
			j = i * i
			while j <= n:
				fs[j] = False
				j += i
		i += 1
	while i <= n:
		if fs[i]:
			rs[pc] = i
			pc += 1
		i += 1
	return (fs, rs[0:pc])
(fs, ps) = builderPrime(100000)

def fact(ps, n):
	rs = []
	i = 0
	sgn = int(pow(n, 0.5) + 1e-05)
	while ps[i] <= sgn:
		t = ps[i]
		while not n % t:
			n //= t
			rs.append(t)
		i += 1
	if n > 1:
		rs.append(n)
	return rs
for _ in range(int(input())):
	(n, s) = (int(input()), 0)
	for x in input().split(' '):
		xi = int(x)
		if xi > 1:
			fs = fact(ps, xi)
			i = 0
			while xi % 2 == 0:
				xi >>= 1
				i += 1
			s ^= len(fs) - i + 1 if i > 1 else len(fs)
	print(1 if s else 2)


import math

def count_prime_factors(n):
	c = 0
	if n % 2 == 0:
		c += 1
	while n % 2 == 0:
		n /= 2
	i = 3
	while i * i <= n:
		while n % i == 0:
			n /= i
			if i % 2 != 0:
				c += 1
		i += 1
	if n > 2:
		c += 1
	return c
t = int(input())
for _ in range(t):
	n = int(input())
	L = list(map(int, input().split(' ')))
	s = 0
	ans = map(count_prime_factors, L)
	for i in ans:
		s = s ^ i
	if s != 0:
		print(1)
	else:
		print(2)


import sys
from time import time

def nimbers(h):

	def mex(cache):
		r = 0
		while r in cache:
			r += 1
		return r
	(nn, cache) = ([0], set())
	for l in range(1, h + 1):
		cache.clear()
		rt = int(pow(l, 0.5))
		for a in range(1, rt + 1):
			if l % a == 0:
				b = l // a
				for (y, z) in ((a, b), (b, a)):
					if y % 2 == 0:
						u = 0
						cache.add(u)
					elif y > 1:
						u = nn[z]
						cache.add(u)
		m = mex(cache)
		nn.append(m)
	return nn

def solve(hh, nn):
	rval = 0
	for h in hh:
		rval ^= nn[h]
	return rval != 0
tm = time()
N = pow(10, 5)
nn = nimbers(N)
print('nimbers generated: %s, %s' % (time() - tm, nn[:20]), file=sys.stderr)
t = int(input())
for _ in range(t):
	_ = int(input())
	hh = list(map(int, input().split()))
	if solve(hh, nn):
		print(1)
	else:
		print(2)
print('time elapsed: %s' % (time() - tm,), file=sys.stderr)


def oddprimefactor(n):
	c = 0
	if n % 2 == 0:
		c += 1
	while n % 2 == 0:
		n /= 2
	i = 3
	while i * i <= n:
		while n % i == 0:
			n /= i
			if i % 2 != 0:
				c += 1
		i += 1
	if n > 2:
		c += 1
	return c
for _ in range(int(input())):
	n = int(input())
	towers = map(int, input().split())
	ans = map(oddprimefactor, towers)
	x = 0
	for i in ans:
		x ^= i
	print(2 if x == 0 else 1)


primes = [2]
for p in range(3, 400, 2):
	for q in primes:
		if p % q == 0:
			break
		if q * q > p:
			primes.append(p)
			break

def height(n):
	h = 0
	while n % 4 == 0:
		n /= 2
	for p in primes:
		if n == 1:
			break
		while n % p == 0:
			(n, h) = (n / p, h + 1)
	return h + (n > 1)
from functools import reduce
for _ in range(int(input())):
	n = int(input())
	h = list(map(int, input().split()))
	print(1 + (reduce(lambda x, y: x ^ y, map(height, h)) == 0))


import math

def find(v):
	for i in range(1, len(v)):
		if v[i] - v[i - 1] > 1:
			return v[i - 1] + 1
	return v[len(v) - 1] + 1
g = [0] * 100003
for i in range(2, 100001):
	p = int(math.sqrt(i))
	v = []
	for j in range(1, p + 1):
		if i % j == 0:
			if j % 2:
				v.append(g[i // j])
			if i // j % 2:
				v.append(g[j])
	v.sort()
	g[i] = v[0] - 1 if v[0] > 0 else find(v)
t = int(input())
for _ in range(t):
	n = int(input())
	h = [int(x) for x in input().split()]
	r = 0
	for i in range(n):
		r = r ^ g[h[i]]
	if r:
		print(1)
	else:
		print(2)


import os
import sys
import math

def oddprimefactor(n):
	c = 0
	if n % 2 == 0:
		c += 1
	while n % 2 == 0:
		n /= 2
	i = 3
	while i * i <= n:
		while n % i == 0:
			n /= i
			if i % 2 != 0:
				c += 1
		i += 1
	if n > 2:
		c += 1
	return c
t = int(input())
for i in range(t):
	arr_count = int(input())
	arr = []
	value = 0
	arr = list(map(int, input().split()))
	for i in arr:
		value = value ^ oddprimefactor(i)
	if value == 0:
		print(2)
	else:
		print(1)


from functools import reduce
N = 1000007
even = [0] * N
odd = [0] * N
for i in range(2, N, 2):
	x = i
	while x % 2 == 0:
		even[i] += 1
		x /= 2
for d in range(3, N, 2):
	if not odd[d]:
		for i in range(d, N, d):
			x = i
			while x % d == 0:
				odd[i] += 1
				x /= d

def g(x):
	e = even[x]
	o = odd[x]
	if e == 0:
		return o
	else:
		return o + 1
for _ in range(int(input())):
	n = int(input())
	a = map(int, input().split())
	a = map(g, a)
	xor = reduce(lambda x, y: x ^ y, a)
	if xor:
		print(1)
	else:
		print(2)


def oddprimefactor(n):
	c = 0
	if n % 2 == 0:
		c += 1
	while n % 2 == 0:
		n /= 2
	i = 3
	while i * i <= n:
		while n % i == 0:
			n /= i
			if i % 2 != 0:
				c += 1
		i += 1
	if n > 2:
		c += 1
	return c
for _ in range(int(input())):
	n = int(input())
	towers = list(map(int, input().split()))
	ans = list(map(oddprimefactor, towers))
	x = 0
	for i in ans:
		x ^= i
	print(2 if x == 0 else 1)


def sieve_grundy(N=10 ** 5 + 1):
	G = [0] * N
	for k in range(2, N, 2):
		G[k] = 1
	for p in range(3, N):
		if G[p] == 0:
			q = p
			while q < N:
				for k in range(q, N, q):
					G[k] += 1
				q *= p
	return G

def main():
	G = sieve_grundy()
	T = int(input())
	for _ in range(T):
		N = int(input())
		H = map(int, input().split())
		g = 0
		for h in H:
			g ^= G[h]
		print(2 if g == 0 else 1)
main()


def oddprimefactor(n):
	c = 0
	if n % 2 == 0:
		c += 1
	while n % 2 == 0:
		n /= 2
	i = 3
	while i * i <= n:
		while n % i == 0:
			n /= i
			if i % 2 != 0:
				c += 1
		i += 1
	if n > 2:
		c += 1
	return c
for _ in range(int(input())):
	n = int(input())
	towers = map(int, input().split())
	ans = map(oddprimefactor, towers)
	x = 0
	for i in ans:
		x ^= i
	print(2 if x == 0 else 1)


import functools, operator
LIMIT = 10 ** 5
TOWER_VALUE = [0] * (LIMIT + 1)
TOWER_VALUE[0] = TOWER_VALUE[1] = 0
for i in range(2, LIMIT + 1, 2):
	TOWER_VALUE[i] += 1
for i in range(3, LIMIT + 1, 2):
	if TOWER_VALUE[i] > 0:
		continue
	prime = shift = i
	while shift <= LIMIT:
		for j in range(shift, LIMIT + 1, shift):
			TOWER_VALUE[j] += 1
		shift *= prime

def tower_value(x):
	return TOWER_VALUE[x]

def nims_game(iterable):
	return functools.reduce(operator.xor, iterable) > 0
output_buffer = []
test_count = int(input())
for _ in range(test_count):
	tower_count = int(input())
	tower_sizes = list(map(int, input().split()))
	winnable = nims_game(map(tower_value, tower_sizes))
	output_buffer.append('1' if winnable else '2')
print(*output_buffer, sep='\n')


from functools import reduce

def mex(s):
	f = 0
	m = max(s)
	for i in range(m):
		if i not in s:
			return i
	return m + 1

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

def grundy(n):
	if n in [0, 1]:
		return 0
	s = {0}
	f = factors(n) - {1, n}
	for e in f:
		if e % 2 == 1:
			s.add(grundy(int(n / e)))
	return mex(s)
t = int(input().strip())
for each in range(t):
	n = int(input().strip())
	arr = [int(i) for i in input().strip().split(' ')]
	g = grundy(arr[0])
	for i in range(1, n):
		g ^= grundy(arr[i])
	if g == 0:
		print('2')
	else:
		print('1')


import os
import sys
from collections import Counter

def prime(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 Counter(factors)

def grundy(n):
	if n == 1:
		return 0
	s = dict(prime(n))
	x = 0
	for each in s:
		if each % 2:
			x += s[each]
	return x + 1 if n % 2 == 0 else x
t = int(input().strip())
for each in range(t):
	n = int(input().strip())
	arr = [int(i) for i in input().strip().split(' ')]
	g = grundy(arr[0])
	for i in range(1, n):
		g ^= grundy(arr[i])
	if g == 0:
		print('2')
	else:
		print('1')


import sys
from collections import defaultdict
sys.setrecursionlimit(1000000)

def mex(gset):
	i = 0
	while True:
		if i not in gset:
			return i
		i += 1

def Grundy(n):
	try:
		return mem[n]
	except:
		Z = 2
		arr = set()
		arr.add(0)
		while Z <= n ** 0.5:
			if n % Z == 0:
				d = n // Z
				if d % 2 != 0:
					arr.add(Grundy(Z))
				if Z % 2 != 0:
					arr.add(Grundy(d))
			Z += 1
		mem[n] = mex(arr)
		return mem[n]
T = int(input())
mem = defaultdict()
mem[0] = 0
mem[1] = 0
mem[2] = 1
for t in range(T):
	N = int(input())
	piles = list(map(int, input().split()))
	xor = 0
	for ele in piles:
		xor ^= Grundy(ele)
	if xor == 0:
		print(2)
	else:
		print(1)


from math import sqrt
result = list()
for i in range(int(input())):
	s = int(input())
	m = list(map(int, input().split(' ')))
	ar = list()
	for n in m:
		r = 2
		q = 0
		u = 0
		g = 0
		while True:
			if n % r == 0:
				n = n // r
				if r != 2:
					q += 1
				else:
					if g == 0:
						q += 1
					g += 1
			else:
				r += 1
				if r > sqrt(n):
					if n > 1:
						q += 1
					break
			if n == 0:
				break
		while True:
			b = q % 2
			q = q // 2
			u += 1
			if len(ar) < u:
				ar.append(b)
			else:
				ar[u - 1] = (ar[u - 1] + b) % 2
			if q == 0:
				break
	if ar.count(1) > 0:
		result.append('1')
	else:
		result.append('2')
print('\n'.join(result))


import os
import sys
a = [0]
for N in range(1, 10 ** 5 + 1):
	i = N
	twos = 0
	c = 0
	while N % 2 == 0:
		N //= 2
		twos = 1
	d = 3
	while d * d <= N:
		while N % d == 0:
			c = c + 1
			N //= d
		d = d + 2
	if N > 1:
		c = c + 1
	a.append(c + twos)
for _ in range(int(input())):
	input()
	r = 0
	for h in map(int, input().split()):
		r ^= a[h]
	print(1 if r else 2)