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, and both players always move optimally.
Initially there are $N$ towers of various heights.
The players move in alternating turns. In each turn, a player can choose a tower of height $\mbox{X}$ and reduce its height to $\mathbf{Y}$, where $1\leq Y<X$ and $\mathbf{Y}$ evenly divides $\mbox{X}$.
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? 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. 

Each of the $2T$ subsequent lines defines a test case. Each test case is described over the following 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\leq100$
$1\leq N\leq100$
$1\leq h_i\leq10^6$

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

Test Case 0: 

Player $\mbox{1}$ reduces the second tower to height $\mbox{1}$ and subsequently wins.

Test Case 1: 

There are two possible moves:

Reduce the second tower to $\mbox{1}$ 
Reduce the third tower to $\mbox{1}$. 

Whichever move player $\mbox{1}$ makes, player $2$ will make the other move. Thus, player $2$ wins.

Source: hackerrank | Difficulty: MEDIUM
Tags: Game theory


Solutions:
def nim_sum(a, n):
	ans = 0
	for i in range(n):
		ans = ans ^ a[i]
	return ans
t = int(input())
while t != 0:
	t -= 1
	n = int(input())
	a = [int(i) for i in input().split()]
	b = [0 for i in range(n)]
	for i in range(n):
		if a[i] == 1:
			b[i] = 0
		else:
			b[i] = 0
			j = 2
			root = int(pow(a[i], 0.5))
			while a[i] != 1 and j <= root:
				if a[i] % j == 0:
					while a[i] % j == 0:
						b[i] += 1
						a[i] = a[i] // j
				j += 1
			if a[i] != 1:
				b[i] += 1
	ans = nim_sum(b, n)
	if ans != 0:
		print('1')
	else:
		print('2')


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)
from functools import reduce

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 == 1:
		return 0
	s = dict(prime(n))
	x = 0
	for each in s:
		x += s[each]
	return 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')


t = int(input())

def no_fact(x):
	ans = 0
	n = x
	while n % 2 == 0:
		n = int(n / 2)
		ans += 1
	while n % 3 == 0:
		n = int(n / 3)
		ans += 1
	i = 5
	while i * i <= n:
		while n % i == 0:
			n = int(n / i)
			ans += 1
		if i % 6 == 5:
			i += 2
		elif i % 6 == 1:
			i += 4
	if n > 1:
		ans += 1
	return ans
for ii in range(t):
	n = int(input())
	l = 0
	for i in input().split():
		x = int(i)
		if x == 1:
			ans = 0
		else:
			ans = max(1, no_fact(x))
		l = l ^ ans
	if l == 0:
		print('2')
	else:
		print('1')


import math

def count_prime_factors(n):
	if n in [-1, 0, 1]:
		return 0
	if n % 2 == 0:
		return 1 + count_prime_factors(n / 2)
	else:
		for j in range(3, int(math.sqrt(n)) + 1, 2):
			if n % j == 0:
				return 1 + count_prime_factors(n / j)
	return 1
t = int(input().strip())
for i in range(t):
	input().strip()
	h_arr = [count_prime_factors(int(x)) for x in input().strip().split(' ') if x != 1]
	nim_sum = 0
	for n in h_arr:
		nim_sum = nim_sum ^ n
	if nim_sum != 0:
		print(1)
	else:
		print(2)


def f(n):
	c = 0
	while n % 2 == 0:
		n /= 2
		c += 1
	d = 3
	while d * d <= n:
		while n % d == 0:
			n /= d
			c += 1
		d += 2
	if n > 1:
		c += 1
	return c
T = int(input())
for _ in range(T):
	n = int(input())
	hs = map(int, input().split())
	r = 0
	for h in hs:
		r ^= f(h)
	print(1 if r else 2)


prfcdp = {}

def xor(l):
	res = l[0]
	for n in range(len(l) - 1):
		res = res ^ l[n + 1]
	return res

def prfc(N):
	if prfcdp.get(N, -1) != -1:
		return prfcdp[N]
	(count, n) = (0, N)
	while n % 2 == 0:
		count += 1
		n = n / 2
	(i, I) = (3, n ** 0.5)
	while i <= I:
		while n % i == 0:
			count += 1
			n = n / i
		i += 2
	if n > 2:
		count += 1
	prfcdp[N] = count
	return count
for _ in range(int(input())):
	dummy = input()
	l = list(map(int, input().split()))
	x = list(map(prfc, l))
	if xor(x) == 0:
		print('2')
	else:
		print('1')


from functools import reduce
n = 10 ** 6
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)
primes = [2] + [i for i in range(3, n, 2) if sieve[i]]

def countPrimeFactors(n):
	i = 0
	c = 0
	while n > 1:
		if n % primes[i] == 0:
			c += 1
			n = n // primes[i]
		else:
			i += 1
	return c
for _ in range(int(input())):
	_ = input()
	h = (countPrimeFactors(int(x)) for x in input().split(' '))
	print(1 if reduce(lambda x, y: x ^ y, h) else 2)


def factors(n):
	q = 0
	f = 2
	c = 0
	while 1:
		p = n // f
		if p < f:
			break
		if n % f == 0:
			c += 1
			n = p
		else:
			f += 1
	if n > 1:
		c += 1
	return c
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 ^ factors(h[i])
	if r:
		print(1)
	else:
		print(2)


hmax = 10 ** 6
hlim = 10 ** 3
n_divisors = [1 if i > 1 else 0 for i in range(hmax + 1)]
for i in range(2, hmax + 1):
	j = 2
	while j <= i and i * j <= hmax:
		n_divisors[i * j] = n_divisors[i] + n_divisors[j]
		j += 1

def nim(l):
	k = 0
	for x in l:
		k ^= x
	if k == 0:
		return 2
	return 1
for _ in range(int(input())):
	n = int(input())
	l = [n_divisors[int(x)] for x in input().split()]
	print(nim(l))


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())):
	input()
	x = 0
	for i in map(int, input().split()):
		x ^= grundy(i)
	print(1 if x else 2)


from math import *
from functools import *

def factors(num: int) -> [int]:
	if num == 0:
		return []
	if num == 1:
		return []
	result = []
	for x in range(2, ceil(sqrt(num)) + 1):
		while num != 1 and num % x == 0:
			num = num // x
			result.append(x)
	if num != 1:
		result.append(num)
	return result
T = int(input())
for t in range(T):
	N = int(input())
	towers = [int(x) for x in input().split()]
	sizes = [len(factors(x)) for x in towers]
	y = reduce(lambda x, y: x ^ y, sizes)
	if y != 0:
		print('1')
	else:
		print('2')


nooftests = int(input().strip())

def countnooffactors(no):
	if no < 2:
		return 0
	flags = [True] * no
	flags[0] = False
	flags[1] = False
	for (i, isprime) in enumerate(flags):
		if isprime:
			for j in range(i * i, no, i):
				flags[j] = False
	return sum(flags)
import math

def count_prime_factors(n):
	if n in [-1, 0, 1]:
		return 0
	if n % 2 == 0:
		return 1 + count_prime_factors(n / 2)
	else:
		for j in range(3, int(math.sqrt(n)) + 1, 2):
			if n % j == 0:
				return 1 + count_prime_factors(n / j)
	return 1
for i in range(nooftests):
	nooftowers = int(input().strip())
	towerheights = list(map(int, input().strip().split(' ')))
	test = 0
	for each in towerheights:
		test = test ^ count_prime_factors(each)
	if test == 0:
		print('2')
	else:
		print('1')


import math

def count_prime_factors(n):
	if n in [-1, 0, 1]:
		return 0
	if n % 2 == 0:
		return 1 + count_prime_factors(n / 2)
	else:
		for j in range(3, int(math.sqrt(n)) + 1, 2):
			if n % j == 0:
				return 1 + count_prime_factors(n / j)
	return 1
g = int(input().strip())
for g0 in range(g):
	n = int(input().strip())
	l = list(map(int, input().strip().split(' ')))
	xor = 0
	for num in l:
		xor ^= count_prime_factors(num)
	if xor == 0:
		print('2')
	else:
		print('1')


from functools import reduce
import operator
from math import ceil, sqrt

def read_ints():
	return list(map(int, input().strip().split()))

def div_count(c):
	counter = 0
	for d in range(2, ceil(sqrt(c)) + 1):
		alpha = 0
		while c % d == 0:
			alpha += 1
			c /= d
		counter = alpha + counter
	if c != 1:
		counter += 1
	return counter
assert div_count(1) == 0
assert div_count(7) == 1
assert div_count(4) == 2
assert div_count(6) == 2
(t,) = read_ints()
for _ in range(t):
	(n,) = read_ints()
	tab = read_ints()
	nim_tab = [div_count(c) for c in tab]
	result = reduce(operator.xor, nim_tab, 0)
	print(1 if result 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 = 2
	ret = 0
	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(1000000)

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


from functools import reduce

def primes(n):
	primefac = []
	while n % 2 == 0:
		primefac.append(2)
		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 = [len(primes(int(i))) for i in input().split()]
	temp = reduce(lambda x, y: x ^ y, l)
	if temp == 0:
		print(2)
	else:
		print(1)


from math import sqrt

def pFactors(n):
	(pFact, limit, check, num) = ([], int(sqrt(n)) + 1, 2, n)
	if n == 1:
		return []
	for check in range(2, limit):
		while num % check == 0:
			pFact.append(check)
			num //= check
	if num > 1:
		pFact.append(num)
	return pFact
t = int(input())
for x in range(t):
	n = int(input())
	a = [len(pFactors(int(y))) for y in input().strip().split(' ')]
	xor = 0
	for y in a:
		xor = xor ^ y
	if xor == 0:
		print(2)
	else:
		print(1)


import math

def count_prime(n):
	if n in [0, -1, 1]:
		return 0
	if n % 2 == 0:
		return 1 + count_prime(n // 2)
	else:
		for j in range(3, int(math.sqrt(n) + 1), 2):
			if n % j == 0:
				return 1 + count_prime(n // j)
	return 1
for a in range(int(input())):
	m = int(input())
	anz = 0
	l = [int(i) for i in input().split(' ')]
	for x in l:
		anz ^= count_prime(x)
	if anz:
		print('1')
	else:
		print('2')


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 = 0
	while sieve[x]:
		x //= sieve[x]
		res += 1
	return res
print(*(1 if reduce(xor, map(factors, row), 0) else 2 for row in ar), sep='\n')


nMax = int(1000000.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
T = int(input())
for i1 in range(T):
	input()
	Arr = [len(GetFactors(int(m))) for m in input().strip().split()]
	S = 0
	for i2 in Arr:
		S ^= i2
	print(1) if S != 0 else print(2)


import math

def sieveOfAtkin(limit):
	P = [2, 3]
	sieve = [False] * (limit + 1)
	for x in range(1, int(math.sqrt(limit)) + 1):
		for y in range(1, int(math.sqrt(limit)) + 1):
			n = 4 * x ** 2 + y ** 2
			if n <= limit and (n % 12 == 1 or n % 12 == 5):
				sieve[n] = not sieve[n]
			n = 3 * x ** 2 + y ** 2
			if n <= limit and n % 12 == 7:
				sieve[n] = not sieve[n]
			n = 3 * x ** 2 - y ** 2
			if x > y and n <= limit and (n % 12 == 11):
				sieve[n] = not sieve[n]
	for x in range(5, int(math.sqrt(limit))):
		if sieve[x]:
			for y in range(x ** 2, limit + 1, x ** 2):
				sieve[y] = False
	for p in range(5, limit):
		if sieve[p]:
			P.append(p)
	return P

def factors(n):
	i = 0
	f = 0
	while n > 1:
		if n % P[i] == 0:
			n = n // P[i]
			f += 1
			i = 0
		else:
			i += 1
	return f
P = sieveOfAtkin(10 ** 6)
D = {}
T = int(input())
for t0 in range(T):
	N = int(input())
	C = [int(a) for a in input().split()]
	E = []
	for c in C:
		if c in D:
			E.append(D[c])
		else:
			t = factors(c)
			D[c] = t
			E.append(t)
	x = 0
	for e in E:
		x = x ^ e
	if x == 0:
		print(2)
	else:
		print(1)


import math

def count_prime_factors(n):
	if n in [-1, 0, 1]:
		return 0
	if n % 2 == 0:
		return 1 + count_prime_factors(n / 2)
	else:
		for j in range(3, int(math.sqrt(n)) + 1, 2):
			if n % j == 0:
				return 1 + count_prime_factors(n / j)
	return 1
T = int(input())
for _ in range(T):
	N = int(input())
	a = [int(x) for x in input().strip().split(' ')]
	total = count_prime_factors(a[0])
	for i in range(1, N):
		total = total ^ count_prime_factors(a[i])
	if total == 0:
		print(2)
	else:
		print(1)


import sys
import math
import functools

def numPrimeFactors(n):
	if n <= 1:
		return 0
	if n <= 3:
		return 1
	end = math.sqrt(n)
	for i in range(2, 1 + math.floor(end)):
		if n % i == 0:
			return 1 + numPrimeFactors(math.floor(n / i))
	return 1
T = int(input().strip())
for i in range(T):
	N = int(input().strip())
	h = [int(x) for x in input().strip().split(' ')]
	nimGame = [numPrimeFactors(x) for x in h]
	checksum = functools.reduce(lambda a, b: a ^ b, nimGame)
	if checksum == 0:
		print(2)
	else:
		print(1)


import math

def finddiv(N):
	count = 0
	for i in range(1, int(math.sqrt(N)) + 1):
		if N % i == 0:
			count = count + 1
	if count == 1:
		return 2
	if math.ceil(math.sqrt(N)) == int(math.sqrt(N)):
		return 2 * count - 1
	else:
		return 2 * count
import math
prime = {}

def primefactor(N, count):
	if N == 2:
		return 1 + count
	if N == 3:
		return 1 + count
	if N == 4:
		return 2 + count
	if N == 5:
		return 1 + count
	if N == 6:
		return 2 + count
	if N == 7:
		return 1 + count
	if N == 8:
		return 3 + count
	if N == 9:
		return 2 + count
	if N == 10:
		return 2 + count
	l = int(math.sqrt(N))
	tem = 0
	for i in range(l + 1):
		if i != 0 and i != 1:
			if N % i == 0:
				tem = tem + 1
	if tem == 0:
		return 1 + count
	A = [0 for i in range(l + 1)]
	A[0] = 1
	A[1] = 1
	for i in range(len(A)):
		if A[i] == 0:
			for j in range(2, len(A) // i):
				A[i * j] = 1
	for i in range(len(A)):
		if A[i] == 0:
			prime[i] = 0
	for x in prime:
		if N % x == 0:
			k = x
			return primefactor(N // x, count + 1)
			while N % k == 0:
				prime[x] += 1
				k = k * x
	count = 0
	for x in prime:
		count += prime[x]
	return count

def remove_values_from_list(the_list, val):
	return [value for value in the_list if value != val]

def convert(A):
	for i in range(len(A)):
		A[i] = primefactor(A[i], 0)
	return A

def nim(A):
	countt = A[0]
	for j in range(len(A)):
		if j > 0:
			countt ^= A[j]
	if countt == 0:
		print('2')
	else:
		print('1')
num = int(input())
for i in range(num):
	input()
	A = list(map(int, input().strip().split(' ')))
	A = remove_values_from_list(A, 1)
	A = convert(A)
	nim(A)


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(10000000.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

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

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) 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 ** 6
sieve = set()
primes = [2]
p = 1
while True:
	p += 2
	if p > MAXX:
		break
	if p not in sieve:
		primes.append(p)
		sieve.update((p * x for x in range(p, MAXX // p + 1, 2)))
cache = {1: 0}
cache.update({p: 1 for p in primes})
for elem in range(4, MAXX + 1):
	if elem in cache:
		continue
	for prime in 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)


import math
taillemax = 1000000
orders = [0 for i in range(taillemax + 1)]
primes = set()
noprimes = set()
for i in range(2, math.ceil(math.sqrt(taillemax + 1))):
	if i not in noprimes:
		primes.add(i)
		temp = i
		mult = 2
		while temp * mult <= taillemax:
			noprimes.add(temp * mult)
			mult += 1
for i in range(math.ceil(math.sqrt(taillemax + 1)), taillemax + 1):
	if i not in noprimes:
		primes.add(i)
for i in primes:
	orders[i] = 1
orderedprimes = sorted(list(primes))
for i in range(1, math.ceil(math.log(taillemax + 1, 2))):
	for nombre in range(taillemax):
		if orders[nombre] == i:
			for prime in orderedprimes:
				if prime * nombre > taillemax:
					break
				orders[nombre * prime] = i + 1
t = int(input())
for test in range(t):
	n = int(input())
	towers = [int(i) for i in input().split(' ')]
	temp = 0
	for i in towers:
		temp = temp ^ orders[i]
	if temp == 0:
		print(2)
	else:
		print(1)


from functools import reduce

def numprimefactors(x):
	ans = 0
	d = 2
	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')


def primos(n):
	primfac = []
	d = 2
	while d * d <= n:
		while n % d == 0:
			primfac.append(d)
			n //= d
		d += 1
	if n > 1:
		primfac.append(n)
	return primfac
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 = len(primos(e))
		g ^= p
	if g == 0:
		print(2)
	else:
		print(1)


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 ti in range(t):
	n = int(input())
	a = [int(s) for s in input().split()]
	f = []
	for i in range(n):
		f.append(prime_factors(a[i]))
	c = 0
	for i in f:
		c ^= len(i)
	if c == 0:
		print(2)
	else:
		print(1)


from functools import reduce
from operator import xor

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

def count_factors(n):
	result = 0
	for p in PRIMES:
		if p > n:
			break
		while n % p == 0:
			result += 1
			n /= p
	return result + (n != 1)
for _ in range(int(input())):
	input()
	nim = (count_factors(int(x)) for x in input().split())
	print(1 if reduce(xor, nim) else 2)


import math

def primes(p):
	count = 0
	while p % 2 == 0:
		p = p / 2
		count = count + 1
	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 = primes(a[0])
	for i in range(1, n):
		x = x ^ primes(a[i])
	if x != 0:
		print('1')
	else:
		print('2')


import functools, operator

def prime_sieve(limit):
	primality = [True] * limit
	primality[0] = primality[1] = False
	for (x, prime) in enumerate(primality):
		if prime:
			yield x
			for y in range(x ** 2, limit, x):
				primality[y] = False

def int_root(x, y):

	def approximate_from(a):
		return ((y - 1) * a + x // a ** (y - 1)) // y
	x_curr = x
	x_next = approximate_from(x_curr)
	while x_next < x_curr:
		x_curr = x_next
		x_next = approximate_from(x_curr)
	return x_curr

def prime_factorization(x):
	for prime in prime_sieve(int_root(x, 2) + 1):
		if x == 0:
			break
		exponent = 0
		while True:
			(quotient, remainder) = divmod(x, prime)
			if remainder == 0:
				exponent += 1
				x = quotient
			else:
				break
		if exponent > 0:
			yield (prime, exponent)
	if x > 1:
		yield (x, 1)

def nims_game(iterable):
	return functools.reduce(operator.xor, iterable) > 0
output_buffer = list()
T = int(input())
for _ in range(T):
	N = int(input())
	h = list(map(int, input().split()))
	winnable = nims_game((sum((exponent for (prime, exponent) in prime_factorization(hs))) for hs in h))
	output_buffer.append('1' if winnable else '2')
print('\n'.join(output_buffer))


def primes(n):
	primfac = []
	d = 2
	while d * d <= n:
		while n % d == 0:
			primfac.append(d)
			n //= d
		d += 1
	if n > 1:
		primfac.append(n)
	return len(primfac)
t = int(input().strip())
for t_0 in range(t):
	n = int(input().strip())
	h = [int(i) for i in input().strip().split(' ')]
	sum1 = int(0)
	for j in h:
		sum1 ^= primes(j)
	if sum1 == 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 * 2, len(G), 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 = 2
	primes = 0
	history = [n]
	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 rwh_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 = rwh_primes(1000000)
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:
		s.append(pfactor_counter(t))
	print(nim_game(s))


import math

class Calculator:

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

	def findPrimeCount(self, n):
		result = 1
		if n in self.alreadyFound:
			return self.alreadyFound[n]
		if n == 1:
			self.alreadyFound[1] = 0
			return 0
		lim = math.floor(math.sqrt(n))
		for i in range(2, lim + 2):
			if n % i == 0:
				result = self.findPrimeCount(n / i) + 1
				break
		self.alreadyFound[n] = result
		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.findPrimeCount(k)
		res ^= a
	if res == 0:
		print('2')
	else:
		print('1')


import bisect
import sys
import datetime
import math

def timer(func):

	def new_func(towers):
		then = datetime.datetime.now()
		j = func(towers)
		now = datetime.datetime.now()
		difference = now - then
		print('That took %s.%s seconds' % (difference.seconds, difference.microseconds))
		return j
	return new_func

def populate_primes_with_bisect(x):
	nums = [i for i in range(3, x + 1, 2)]
	primes = [2]
	while True:
		try:
			p = nums.pop(0)
		except:
			break
		primes.append(p)
		j = p ** 2
		while j <= x:
			index = bisect.bisect_left(nums, j)
			try:
				if nums[index] == j:
					nums.pop(index)
			except:
				pass
			j += 2 * p
	return primes

def num_prime_factors(x):
	num_factors = 0
	root = math.sqrt(x)
	for i in primes:
		if i > root:
			break
		while True:
			if x % i == 0:
				num_factors += 1
				x = x // i
			else:
				break
		if x == 1:
			break
	if x != 1:
		num_factors += 1
	return num_factors

def num_factors_list(l):
	num_factors_l = []
	for i in l:
		num_factors_l.append(num_prime_factors(i))
	return num_factors_l

def nim_sum(towers):
	nim_sum = 0
	for t in towers:
		nim_sum = nim_sum ^ t
	return nim_sum
primes = populate_primes_with_bisect(int(math.sqrt(10 ** 6)))
T = int(input().strip())
for game in range(T):
	N = int(input().strip())
	tower_heights = [i for i in map(int, input().strip().split()) if i != 1]
	tower_heights_in_prime_factors = num_factors_list(tower_heights)
	if nim_sum(tower_heights_in_prime_factors) == 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
	for p in primes(sqrt(x)):
		while x > 1 and x % p == 0:
			s += 1
			x //= p
	return s if x == 1 else s + 1

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


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

def getPrimes(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 > 1]
primes = getPrimes(1000001)

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

def solveNip(arr):
	x = 0
	for el in arr:
		x = 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(solveNip(reducedArr))


from math import sqrt
from itertools import takewhile, zip_longest
MAGIC = [4, 8, 10, 14, 16, 20, 26, 28]

def gen_primes(n):
	primes = []
	p_base = 3
	while True:
		for pdiff in MAGIC:
			p = p_base + pdiff
			top = sqrt(p)
			if all((p % factor for factor in takewhile(lambda x: x <= top, primes))):
				primes.append(p)
				if p > n:
					return [2, 3, 5] + primes
		p_base += 30
PRIMES = gen_primes(1000)

def prime_factorization(x):
	prime_index = 0
	prime = PRIMES[prime_index]
	while x > 1:
		if prime > sqrt(x):
			yield x
			break
		if not x % prime:
			yield prime
			x //= prime
		else:
			prime_index += 1
			try:
				prime = PRIMES[prime_index]
			except IndexError:
				raise Exception('Not enough primes generated')

def binary(n):
	b = []
	while n > 0:
		if n % 2:
			b.append(1)
		else:
			b.append(0)
		n //= 2
	return b

def winning(h, verbose=False):
	ns = [sum((1 for _ in prime_factorization(hi))) for hi in h]
	ns = [n for n in ns if n > 0]
	if verbose:
		print('Nim piles: {}'.format(ns))
	b = [binary(n) for n in ns]
	if verbose:
		print('Nim binary: {}'.format(b))
	q = [sum(x) for x in zip_longest(*b, fillvalue=0)]
	if verbose:
		print('Nim balance: {}'.format(q))
	if any((qi % 2 for qi in q)):
		return 1
	else:
		return 2
DEBUG = False
T = int(input())
for _ in range(T):
	n = int(input())
	h = [int(x) for x in input().split()]
	if DEBUG:
		print(h)
	print(winning(h, verbose=DEBUG))


import sys

def primes_gen(n):
	cache = [True] * n
	cache[0] = cache[1] = False
	for p in range(n):
		if cache[p]:
			yield p
			for i in range(p + p, n, p):
				cache[i] = False

def factors_gen(n, pp):
	for p in pp:
		if n == 1:
			break
		cnt = 0
		while n % p == 0:
			cnt += 1
			n //= p
		if cnt:
			yield (p, cnt)
pp = list(primes_gen(pow(10, 6) + 1))

def solve(aa):

	def nimsum(dd):
		ns = 0
		for d in dd:
			ns ^= d
		return ns
	print('aa=%s' % aa, file=sys.stderr)
	dd = []
	for a in aa:
		total = 0
		for (_, cnt) in factors_gen(a, pp):
			total += cnt
		if total:
			dd.append(total)
	print('dd=%s' % dd, file=sys.stderr)
	ns = nimsum(dd)
	ones = dd.count(1)
	print('ns=%d ones=%d' % (ns, ones), file=sys.stderr)
	if ones == len(dd):
		return ones % 2
	return ns > 0
t = int(input())
for _ in range(t):
	_ = int(input())
	aa = list(map(int, input().split()))
	if solve(aa):
		print(1)
	else:
		print(2)


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 numPrimeDivisors(n, primeList):
	count = 0
	if n > 1:
		for prime in primeList:
			while n % prime == 0:
				n = n / prime
				count += 1
	if n > 1:
		count += 1
	return count
p = primes(1001)
for g in range(T):
	N = int(input().strip())
	towers = list(map(int, input().strip().split(' ')))
	a = 0
	for t in towers:
		a = a ^ numPrimeDivisors(t, p)
	if a == 0:
		print(2)
	else:
		print(1)


primes = []
for n in range(2, 2001):
	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
for i in range(int(input())):
	g = 0
	input()
	for j in map(int, input().split()):
		g ^= find_primes(j)
	print([1, 2][g == 0])


import math

def compute_prime_factors(n):
	i = 2
	curr = n
	total = 0
	while curr > 1 and i * i <= n:
		if curr % i == 0:
			curr = curr // i
			total += 1
		else:
			i += 1
	if curr != 1:
		total += 1
	return total

def solve(H):
	for (i, n) in enumerate(H):
		H[i] = compute_prime_factors(n)
	uniques = [0] * 20
	for n in H:
		uniques[n] = (uniques[n] + 1) % 2
	uniques = uniques[1:]
	hs = [i + 1 for (i, v) in enumerate(uniques) if v == 1]
	nim_sum = 0
	for h in hs:
		nim_sum ^= h
	if nim_sum == 0:
		return 2
	else:
		return 1
T = int(input())
for _ in range(T):
	N = int(input())
	H = [int(h) for h in input().split(' ')]
	print(solve(H))


import math

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


a1 = []
for i in range(2, 1000):
	q = 0
	for j in range(2, int(i ** 0.5) + 1):
		if i % j == 0:
			q = 1
			break
	if q == 0:
		a1 += [i]
for _ in range(int(input())):
	(n, s) = (int(input()), 0)
	a = list(map(int, input().split()))
	for i in range(n):
		q = a[i]
		(s1, j, l) = ([[1, 1]], 0, 1)
		try:
			while q > 1:
				if q % a1[j] == 0:
					if a1[j] == s1[-1][0]:
						s1[-1][1] += 1
					else:
						s1 += [[a1[j], 1]]
						l += 1
					q //= a1[j]
					j -= 1
				j += 1
		except:
			s1 += [[q, 1]]
			l += 1
		p = -1
		for r in range(l):
			p += s1[r][1]
		s ^= p
	if s == 0:
		print(2)
	else:
		print(1)


def fact(n):
	if n == 1:
		return 0
	s = int(n ** 0.5 + 1)
	for i in range(2, s):
		if n % i == 0:
			return 1 + fact(n / i)
	else:
		return 1
for _ in range(int(input())):
	n = int(input())
	ls = list(map(int, input().split()))
	ls = list(map(fact, ls))
	x = 0
	for i in ls:
		x = x ^ i
	if x == 0:
		print('2')
	else:
		print('1')


from collections import defaultdict
from functools import reduce, lru_cache
from operator import xor
from math import sqrt
memo = {}

def grundy(n):
	global memo
	if n in memo:
		return memo[n]
	s = set()
	for i in range(1, n):
		if n % i != 0:
			continue
		s.add(grundy(i))
		if i > 1:
			s.add(grundy(n // i))
	g = 0
	while g in s:
		g += 1
	memo[n] = g
	return g

def prime_factor_decomposition(n):
	import math
	m = defaultdict(int)
	while n > 1:
		find_factor = False
		for i in range(2, int(math.sqrt(n)) + 1):
			if n % i == 0:
				m[i] += 1
				n //= i
				find_factor = True
				break
		if not find_factor:
			m[n] += 1
			break
	return m

def main():
	T = int(input())
	for _ in range(T):
		N = int(input())
		tower_list = list(map(int, input().split()))
		grundy_list = []
		for t in tower_list:
			g = sum([v for (k, v) in prime_factor_decomposition(t).items()])
			grundy_list.append(g)
		print('1' if reduce(xor, grundy_list) != 0 else '2')
main()


def nim(l):
	l_ = list((str(bin(b)[2:].zfill(7)) for b in l))
	i = 0
	re = 2
	while True:
		if list((a[i] for a in l_)).count('1') % 2 == 1:
			re = 1
			break
		elif i >= 6:
			break
		else:
			i += 1
	print(re)

def list_prime(n):
	l = [True] * (n + 1)
	l[0] = False
	l[1] = False
	for i in range(2, n):
		if l[i]:
			for j in range(i * 2, n + 1, i):
				l[j] = False
	return l
l = list_prime(1000000)
div2 = list(range(1000001))
div2[0] = 0
div2[1] = 0
for i in range(2, 1000001):
	if l[i]:
		div2[i] = 1
	else:
		j = 1
		while True:
			j += 1
			if i % j == 0:
				div2[i] = 1 + div2[int(i / j)]
				break
for i in range(int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	s = list((div2[a] for a in s))
	nim(s)


def sieve(n):
	sieve = [True] * n
	primes = [2]
	for i in range(3, n):
		if sieve[i]:
			j = i
			primes.append(i)
			while j < n:
				sieve[j] = False
				j += i
	return primes
primes = sieve(1000000)

def countprimes(val):
	cnt = 0
	j = 0
	while val != 1:
		i = primes[j]
		while val % i == 0:
			cnt += 1
			val /= i
		j += 1
	return cnt
t = int(input())
while t != 0:
	t -= 1
	input()
	r = 0
	for v in input().split():
		r ^= countprimes(int(v))
	if r == 0:
		print(2)
	else:
		print(1)


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 countPrimeFactors(n, a):
	if n == 1:
		return 0
	if a[n]:
		return 1
	for i in range(2, n):
		if n % i == 0:
			return 1 + countPrimeFactors(n // i, a)

def main():
	b = sieve(1000000)
	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 range(m):
			x ^= countPrimeFactors(a[j], b)
		print(2 if x == 0 else 1)
main()


def nimGame(pile):
	ans = 0
	for i in range(len(pile)):
		ans = ans ^ pile[i]
	if ans == 0:
		return 2
	else:
		return 1

def numofprimes(n):
	if n == 1:
		return 0
	for p in primes:
		if n % p == 0:
			return numofprimes(n // p) + 1
	return 1
comp = [False] * 2000
for i in range(2, 2000):
	if not comp[i]:
		j = 2
		while i * j < 2000:
			comp[i * j] = True
			j += 1
primes = [i for i in range(2, 2000) if not comp[i]]
t = int(input())
for tt in range(t):
	n = int(input())
	a = [numofprimes(int(x)) for x in input().split()]
	print(nimGame(a))


import functools
import operator

class PrimeStore:

	def __init__(self):
		self.primes = [2, 3, 5, 7]

	def generate_primes(self, max):
		for i in range(self.primes[-1] + 2, int(max + 1), 2):
			ok = True
			for p in self.primes:
				if i % p == 0:
					ok = False
					break
				if p * p > i:
					break
			if ok:
				self.primes.append(i)

	def is_prime(self, num):
		if num == 0 or num == 1:
			return False
		if num in self.primes:
			return True
		for p in self.primes:
			if num % p == 0:
				return False
		return True

	def count_primes(self, num):
		count = 0
		for p in self.primes:
			while num % p == 0:
				num /= p
				count += 1
			if num == 1:
				return count
		raise ValueError('Not enough primes')

def nim_game(piles):
	nim_sum = functools.reduce(operator.xor, piles)
	return nim_sum != 0

def main():
	T = int(input().strip())
	ps = PrimeStore()
	ps.generate_primes(1000000)
	for t in range(T):
		N = input()
		nums = list(map(int, input().strip().split(' ')))
		piles = [ps.count_primes(num) for num in nums]
		print(1 if nim_game(piles) else 2)
main()


def prepare(L):
	F = [1] * (L + 1)
	F[1] = 0

	def first(e):
		(r, mask) = (0, 1)
		while e & mask != 0:
			r += 1
			mask <<= 1
		return r
	for e in range(2, L // 2 + 1):
		F[e] = first(F[e])
		mask = 1 << F[e]
		for d in range(2 * e, L + 1, e):
			F[d] |= mask
	for e in range(L // 2 + 1, L + 1):
		F[e] = first(F[e])
	return F
F = prepare(10 ** 6)

def towerBreakers(H):
	r = 0
	for h in H:
		r = r ^ F[h]
	if 0 == r:
		return 2
	return 1
t = int(input().strip())
for a0 in range(t):
	input()
	H = map(int, input().strip().split(' '))
	result = towerBreakers(H)
	print(result)


def options(h):
	(ans, i) = (0, 2)
	i_hi = int(h ** 0.5)
	while i_hi >= i:
		if h % i == 0:
			ans += 1
			h //= i
			i_hi = int(h ** 0.5)
			i = 2
		else:
			i += 1
	return ans + (h > 1)
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(1000000)

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())):
	input()
	print(1 if functools.reduce(lambda s, d: s ^ d, [len(v) for v in [fact(ps, int(x)) for x in input().split(' ')]], 0) else 2)


import os
import sys

def getFac(a):
	a = int(a)
	if a == 1:
		return 0
	p = [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, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009]
	ans = 0
	i = 0
	while a > 1 and i < len(p):
		if a % p[i] == 0:
			ans += 1
			a = a // p[i]
		else:
			i += 1
	return ans + (1 if a != 1 else 0)

def winner(arr):
	ans = 0
	for i in arr:
		ans = ans ^ i
	if ans == 0:
		return 2
	return 1
t = int(input().strip())
for t_i in range(t):
	n = int(input().strip())
	arr = list(map(getFac, input().strip().split()))
	print(winner(arr))


import math

def count_prime_factors(n):
	if n in [-1, 0, 1]:
		return 0
	if n % 2 == 0:
		return 1 + count_prime_factors(n / 2)
	else:
		for j in range(3, int(math.sqrt(n)) + 1, 2):
			if n % j == 0:
				return 1 + count_prime_factors(n / j)
	return 1
t = int(input())
for _ in range(t):
	n = int(input())
	L = list(map(int, input().split(' ')))
	s = 0
	for i in range(n):
		s = s ^ count_prime_factors(L[i])
	if s != 0:
		print(1)
	else:
		print(2)


primes = []
primes_set = set()
mult_counts = [0] * 1000001
for i in range(2, 1000001):
	is_prime = True
	for p in primes:
		if p ** 2 > i:
			break
		if i % p == 0:
			mult_counts[i] = mult_counts[i // p] + 1
			is_prime = False
			break
	if is_prime:
		primes.append(i)
		primes_set.add(i)
		mult_counts[i] = 1
for _ in range(int(input())):
	n = int(input())
	h = [int(hi) for hi in input().split(' ')]
	x = 0
	for hi in h:
		mc = mult_counts[hi]
		x ^= mc
	if x == 0:
		print(2)
	else:
		print(1)


lim = 1000
primes = [2]
flags = bytearray(lim)
for i in range(3, lim, 2):
	if flags[i]:
		continue
	primes.append(i)
	for j in range(3 * i, lim, 2 * i):
		flags[j] = 1
T = int(input())
for t in range(T):
	N = int(input())
	h = [int(x) for x in input().split()]
	x = 0
	for n in h:
		f = 0
		for p in primes:
			while n % p == 0:
				n //= p
				f += 1
		if n > 1:
			f += 1
		x ^= f
	print(1 if x else 2)


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

def height(tower):
	h = 0
	for p in primes:
		while tower % p == 0:
			tower /= p
			h += 1
		if tower == 1:
			break
	if tower > 1:
		h += 1
	return h
for _ in range(int(input())):
	n = int(input())
	h = list(map(int, input().split()))
	assert len(h) == n and min(h) >= 1 and (max(h) <= 10 ** 6)
	x = 0
	for tower in h:
		x = x ^ height(tower)
	print([1, 2][x == 0])


def pfc(n):
	if n == 1 or n == 0:
		return 0
	c = 0
	from math import sqrt as S
	for i in range(2, int(S(n)) + 1):
		if n % i == 0:
			while n % i == 0:
				c += 1
				n = n // i
	if n > 1:
		c += 1
	return c
for _ in range(int(input())):
	n = int(input())
	l = [int(i) for i in input().split()]
	G = [pfc(i) for i in l]
	x = 0
	for i in G:
		x = x ^ i
	if x == 0:
		print(2)
	else:
		print(1)


import math

def count_prime_factors(n):
	if n in [-1, 0, 1]:
		return 0
	if n % 2 == 0:
		return 1 + count_prime_factors(n / 2)
	else:
		for j in range(3, int(math.sqrt(n)) + 1, 2):
			if n % j == 0:
				return 1 + count_prime_factors(n / j)
	return 1
t = int(input().strip())
for i in range(t):
	input().strip()
	h_arr = [count_prime_factors(int(x)) for x in input().strip().split(' ') if x != 1]
	nim_sum = 0
	for n in h_arr:
		nim_sum = nim_sum ^ n
	if nim_sum != 0:
		print(1)
	else:
		print(2)


import math
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	nimSum = 0
	for i in arr:
		numOfPrimeFactors = 0
		if i == 1:
			numOfPrimeFactors = 0
		elif i != 0 and (not i & i - 1):
			numOfPrimeFactors = i // 2
		else:
			while i > 1:
				flag = False
				for j in range(2, int(math.sqrt(i)) + 1):
					if i % j == 0:
						numOfPrimeFactors += 1
						i //= j
						flag = True
						break
				if not flag:
					numOfPrimeFactors += 1
					break
		nimSum = nimSum ^ numOfPrimeFactors
	if nimSum != 0:
		print('1')
	else:
		print('2')


import os
import sys
import math
t = int(input())

def count_prime_factors(num):
	count = 0
	while num % 2 == 0:
		num /= 2
		count += 1
	for i in range(3, int(math.sqrt(num) + 1), 2):
		while num % i == 0:
			num /= i
			count += 1
	if num > 2:
		count += 1
	return count
for i in range(t):
	arr_count = int(input())
	arr = []
	value = 0
	arr = list(map(int, input().split()))
	for i in arr:
		value = value ^ count_prime_factors(i)
	if value == 0:
		print(2)
	else:
		print(1)


import math

def count_prime_factors(n):
	if n in [-1, 0, 1]:
		return 0
	if n % 2 == 0:
		return 1 + count_prime_factors(n / 2)
	else:
		for j in range(3, int(math.sqrt(n)) + 1, 2):
			if n % j == 0:
				return 1 + count_prime_factors(n / j)
	return 1
t = int(input().strip())
for i in range(t):
	input().strip()
	h_arr = [count_prime_factors(int(x)) for x in input().strip().split(' ') if x != 1]
	nim_sum = 0
	for n in h_arr:
		nim_sum = nim_sum ^ n
	if nim_sum != 0:
		print(1)
	else:
		print(2)


from functools import reduce
N = 1000007
p = [0] * N
for d in range(2, N):
	if not p[d]:
		for i in range(d, N, d):
			x = i
			while x % d == 0:
				p[i] += 1
				x /= d
for _ in range(int(input())):
	n = int(input())
	a = map(int, input().split())
	a = map(lambda x: p[x], a)
	xor = reduce(lambda x, y: x ^ y, a)
	if xor:
		print(1)
	else:
		print(2)