!/bin/python3

import os import sys import math #

Complete the towerBreakers function below.

# def towerBreakers(arr): # # Write your code here. # d=0 for x in arr: d^=primeFactors(x) if(d!=0): return 1 else: return 2

def primeFactors(n): count=0 flag= True while n % 2 == 0: if(flag): count+=1 flag=False n = n / 2 for i in range(3,int(math.sqrt(n))+1,2): while n % i== 0: count+=1 n = n / i
if n > 2: count+=1 return count

if name == 'main': fptr = open(os.environ['OUTPUT_PATH'], 'w')

t = int(input())

for t_itr in range(t):
    arr_count = int(input())

    arr = list(map(int, input().rstrip().split()))

    result = towerBreakers(arr)

    fptr.write(str(result) + '\n')

fptr.close()