A number is algebraic if it is a root of some nonzero polynomial with integer coefficients. A number is transcendental if it is not algebraic.

For example, ${11}$, ${i}$, $\sqrt[3]{2}$ and $\phi$ (golden ratio) are algebraic, because they are roots of $x-11$, $x^2+1$, $x^3-2$ and $x^2-x-1$, respectively. Also, it can be shown that the sum and product of two algebraic numbers is also algebraic, so for example $24+i$, $\sqrt{2}+\sqrt{3}$ and $\sqrt[3]{{11}}\phi$ are also algebraic. However, it has been shown by Lindemann that ${\pi}$ is transcendental.

The degree of an algebraic number is the minimal degree of a polynomial with integer coefficients in which it is a root. For example, the degrees of $5$, ${i}$, $\sqrt[3]{2}$ and $\phi$ are ${1}$, $2$, $3$ and $2$, respectively.

Given $N$ positive integers ${A_1}$, ${A_{2}}$, ..., ${A}_N$, calculate the degree of the following algebraic number:
$\sqrt{A_1}+\sqrt{A_2}+\sqrt{A_3}+\text{}\cdots+\sqrt{A_N}$  

Input Format 

The first line of input contains ${T}$, the number of test cases. The descriptions of the test cases follow.

Each test case has two lines of input. The first line contains a single integer, $N$. The second line contains $N$ integers ${A_1}$, ..., $A_N$ separated by single spaces.

Output Format 

For each test case, output one line containing exactly one integer, which is the answer for that test case.

Constraints 

$1\leq T\leq10^5$ 

$1\leq N\leq50$ 

$1\leq A_i\leq10^7$ 

The sum of the $N$'s in a single test file is at most $10^{5}$  

Sample Input  

3
1
4
3
2 4 4
4
1 2 3 5

Sample Output 

1
2
8

Explanation 

Case 1: A minimal polynomial of $\sqrt{4}$ is $2x-4$.  

Case 2: A minimal polynomial of $\sqrt{2}+\sqrt{4}+\sqrt{4}$ is $x^2-8x+14$.  

Case 3: A minimal polynomial of $\sqrt1+\sqrt{2}+\sqrt{3}+\sqrt{5}$ is:
$x^8-8x^7-12x^6+184x^5-178x^4-664x^3+580x^2+744x-71$

Difficulty: HARD
Tags: Number theory

Starter code:

Solutions:
MAXA = 10 ** 7

def main():
	ncases = int(input())
	for _ in range(ncases):
		n = int(input())
		a = [int(f) for f in input().split()]
		assert n == len(a)
		print(mindegree(a))

def mindegree(a):
	factors = [set(factoroddpow(item)) for item in a]
	adjoins = 0
	for (i, factor) in enumerate(factors):
		if len(factor) == 0:
			continue
		sample = next(iter(factor), None)
		for otherfactor in factors[i + 1:]:
			if sample in otherfactor:
				otherfactor ^= factor
		adjoins += 1
	return 1 << adjoins

def allprimes(upto):
	primes = []
	seive = [True] * (upto + 1)
	for i in range(2, upto + 1):
		if seive[i]:
			primes.append(i)
			for j in range(i * i, upto + 1, i):
				seive[j] = False
	return primes

def factoroddpow(n, primelist=allprimes(int(MAXA ** 0.5))):
	ans = []
	for prime in primelist:
		if n % prime == 0:
			deg = 0
			while n % prime == 0:
				n //= prime
				deg += 1
			if deg & 1 == 1:
				ans.append(prime)
	if n > 1:
		ans.append(n)
	return ans
main()


MAXA = 10 ** 7

def main():
	ncases = int(input())
	for _ in range(ncases):
		n = int(input())
		a = [int(f) for f in input().split()]
		assert n == len(a)
		print(mindegree(a))

def mindegree(a):
	factors = [set(factoroddpow(item)) for item in a]
	adjoins = 0
	for (i, factor) in enumerate(factors):
		if len(factor) == 0:
			continue
		sample = next(iter(factor), None)
		for otherfactor in factors[i + 1:]:
			if sample in otherfactor:
				otherfactor ^= factor
		adjoins += 1
	return 1 << adjoins

def allprimes(upto):
	primes = []
	seive = [True] * (upto + 1)
	for i in range(2, upto + 1):
		if seive[i]:
			primes.append(i)
			for j in range(i * i, upto + 1, i):
				seive[j] = False
	return primes

def factoroddpow(n, primelist=allprimes(int(MAXA ** 0.5))):
	ans = []
	for prime in primelist:
		if n % prime == 0:
			deg = 0
			while n % prime == 0:
				n //= prime
				deg += 1
			if deg & 1 == 1:
				ans.append(prime)
	if n > 1:
		ans.append(n)
	return ans
main()


import math

def is_prime(k):
	small = [2, 3, 5]
	if k in small:
		return True
	if k % 2 == 0:
		return False
	odd = k - 1
	e = 0
	while odd % 2 == 0:
		e += 1
		odd = odd // 2
	for p in small:
		num = pow(p, odd, k)
		check = False
		if num == 1 or num == k - 1:
			continue
		for i in range(e):
			num = pow(num, 2, k)
			if num == k - 1:
				check = True
				break
			if num == 1:
				return False
		if not check and num != 1:
			return False
	return True

def factor(n):
	d = dict()
	l = [i for i in range(1, 30) if i % 2 != 0 and i % 3 != 0 and (i % 5 != 0)]
	x = 0
	sq = math.sqrt(n)
	while x * 30 < sq:
		arr = [i + 30 * x for i in l]
		if x == 0:
			arr.pop(0)
			arr.append(2)
			arr.append(3)
			arr.append(5)
		for div in arr:
			while n % div == 0:
				if div in d:
					d[div] += 1
				else:
					d[div] = 1
				n = n // div
			sq = math.sqrt(n)
		x += 1
		if n == 1 or is_prime(n):
			break
	if n != 1:
		d[n] = 1
	return d

def clean(d):
	d2 = set()
	for (key, val) in d.items():
		if val % 2 == 1:
			d2.add(key)
	return d2

def factor_base(primes, num):
	s = set()
	if len(primes) > 0:
		for p in primes:
			keep = False
			worked = False
			while num % p == 0:
				worked = True
				keep = not keep
				num = num // p
			if worked and keep:
				s.add(p)
			if num == 1:
				break
		if num > 1:
			if is_prime(num):
				s.add(num)
				return s
			else:
				d = factor(num)
				d = clean(d)
				s = s.union(d)
				return s
		return s
	return clean(factor(num))

def row_swap(A, i, j):
	(A[i], A[j]) = (A[j], A[i])

def row_xor(A, i, j):
	A[j] = [(A[i][k] + A[j][k]) % 2 for k in range(len(A[0]))]

def row_reduce(M):
	i = 0
	j = 0
	while i < len(M) and j < len(M[0]):
		if M[i][j] != 1:
			piv = i
			while piv < len(M) and M[piv][j] != 1:
				piv += 1
			if piv == len(M):
				j += 1
				continue
			row_swap(M, i, piv)
		for k in range(i + 1, len(M)):
			if M[k][j] == 1:
				row_xor(M, i, k)
		i += 1
	return i

def sq_detect(n):
	sq = int(math.sqrt(n))
	if n == sq ** 2 or n == (sq + 1) ** 2:
		return True
	return False
for _ in range(int(input())):
	n = int(input())
	if n == 1:
		num = int(input())
		if sq_detect(num):
			print(1)
		else:
			print(2)
	else:
		nums = list(map(int, input().split()))
		facts = []
		ps = set()
		for num in nums:
			d = factor_base(ps, num)
			if len(d) > 0:
				facts.append(d)
				ps = ps.union(d)
		ps = list(ps)
		arr = []
		for d in facts:
			l = []
			for p in ps:
				if p in d:
					l.append(1)
				else:
					l.append(0)
			arr.append(l)
		if len(arr) == 0:
			print(1)
		elif len(arr) == 1:
			print(2)
		else:
			print(pow(2, row_reduce(arr)))


import os, sys, math, itertools
from collections import Counter

def primes_list(n):
	a = [True] * (n + 1)
	a[0] = a[1] = False
	p = 2
	c = 0
	while p <= n:
		c += 1
		for i in range(p + p, n + 1, p):
			a[i] = False
		p += 1
		while p <= n and (not a[p]):
			p += 1
	return [i for i in range(2, n + 1) if a[i]]
PRIMES = [None]

def prime_factorization(x, tableSize=10000):
	primes = PRIMES[0]
	if primes is None:
		primes = PRIMES[0] = primes_list(tableSize)
	counts = Counter()
	pi = 0
	p = primes[pi]
	while x != 1:
		while True:
			(q, r) = divmod(x, p)
			if r != 0:
				break
			counts[p] += 1
			x = q
		if pi < len(primes) - 1:
			pi += 1
			p = primes[pi]
		else:
			p += 2
		if p * p > x:
			break
	if x != 1:
		counts[x] += 1
	return counts

def powerset(iterable):
	s = list(iterable)
	return itertools.chain.from_iterable((itertools.combinations(s, r) for r in range(len(s) + 1)))

def gf2_span_dim(vecs):
	v1 = vecs.copy()
	v2 = set()
	dim = 0
	while v1:
		x = v1[0]
		if x == 0:
			raise ValueError()
		dim += 1
		b = x & -x
		for i in range(1, len(v1)):
			y = v1[i]
			if y & b == 0:
				v2.add(y)
			elif y ^ x != 0:
				v2.add(y ^ x)
		v1 = list(v2)
		v2 = set()
	return dim

def gf2_span_dim_brute(vecs):
	vals = set()
	for s in powerset(vecs):
		y = 0
		for x in s:
			y ^= x
		vals.add(y)
	return len(vals).bit_length() - 1

def degree_of_sum_of_square_roots(As):
	primes = set()
	primeSets = set()
	for a in As:
		pf = prime_factorization(a)
		aprimes = [p for (p, c) in pf.items() if c % 2 == 1]
		if not aprimes:
			continue
		aprimes = tuple(sorted(aprimes))
		primeSets.add(aprimes)
		for p in aprimes:
			primes.add(p)
	bvecs = []
	primeToBit = {p: 2 ** i for (i, p) in enumerate(sorted(primes))}
	for ps in primeSets:
		bvecs.append(sum([primeToBit[p] for p in ps]))
	bvdim = gf2_span_dim(bvecs)
	return 2 ** bvdim

def main():
	T = int(sys.stdin.readline())
	for _ in range(T):
		N = int(sys.stdin.readline())
		As = list(map(int, sys.stdin.readline().strip().split()))
		y = degree_of_sum_of_square_roots(As)
		print(y)
main()


maxprime = 100000
isprime = [True] * maxprime
primelist = []
for i in range(2, maxprime):
	if isprime[i]:
		primelist.append(i)
		for j in range(i * i, maxprime, i):
			isprime[j] = False

def factor(n):
	curr = n
	toret = dict()
	for p in primelist:
		numreps = 0
		while curr % p == 0:
			numreps += 1
			curr //= p
		if numreps > 0:
			toret[p] = numreps
		if p * p > curr:
			break
	if curr != 1:
		toret[curr] = 1
	return toret

def reducepivs(mat, m, n):
	numpivots = 0
	for i in range(n):
		for j in range(numpivots, m):
			if mat[j][i] == 1:
				break
		if mat[j][i] == 1:
			temp = mat[numpivots]
			mat[numpivots] = mat[j]
			mat[j] = temp
			for k in range(numpivots + 1, m):
				if mat[k][i] == 1:
					for l in range(n):
						mat[k][l] = (mat[k][l] + mat[numpivots][l]) % 2
			numpivots += 1
		if numpivots == m:
			break
	return numpivots
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	mat = []
	allprimes = set()
	for i in a:
		ifact = factor(i)
		for p in ifact.keys():
			if ifact[p] % 2 == 1:
				allprimes.add(p)
	for i in a:
		toadd = []
		ifact = factor(i)
		for p in allprimes:
			try:
				toadd.append(ifact[p] % 2)
			except:
				toadd.append(0)
		mat.append(toadd)
	print(pow(2, reducepivs(mat, n, len(allprimes))))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


MAXA = 10 ** 7

def main():
	ncases = int(input())
	for _ in range(ncases):
		n = int(input())
		a = [int(f) for f in input().split()]
		assert n == len(a)
		print(mindegree(a))

def mindegree(a):
	factors = [set(factoroddpow(item)) for item in a]
	adjoins = 0
	for (i, factor) in enumerate(factors):
		if len(factor) == 0:
			continue
		sample = next(iter(factor), None)
		for otherfactor in factors[i + 1:]:
			if sample in otherfactor:
				otherfactor ^= factor
		adjoins += 1
	return 1 << adjoins

def allprimes(upto):
	primes = []
	seive = [True] * (upto + 1)
	for i in range(2, upto + 1):
		if seive[i]:
			primes.append(i)
			for j in range(i * i, upto + 1, i):
				seive[j] = False
	return primes

def factoroddpow(n, primelist=allprimes(int(MAXA ** 0.5))):
	ans = []
	for prime in primelist:
		if n % prime == 0:
			deg = 0
			while n % prime == 0:
				n //= prime
				deg += 1
			if deg & 1 == 1:
				ans.append(prime)
	if n > 1:
		ans.append(n)
	return ans
main()


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr ** 2 <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p ** 2 > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import compress
n_max = int(10 ** 3.5)

def sieve_primes(N):
	if N < 2:
		return []
	if N == 2:
		return [2]
	N = N - 1 | 1
	half = N >> 1
	sieve = bytearray([True]) * (half + 1)
	sieve[0] = False
	for i in range(3, int(N ** 0.5) + 1, 2):
		if sieve[i >> 1]:
			sieve[i * i >> 1::i] = bytearray((N // i - i >> 1) + 1)
	return [2, *compress(range(3, N + 1, 2), sieve[1:])]
primes = sieve_primes(n_max)

def factor(n):
	ret = set()
	m = 1
	for p in primes:
		if p * p > n:
			break
		e = 0
		while n % p == 0:
			n //= p
			e += 1
		if e & 1:
			ret.add(p)
			m *= p
	if n > 1:
		ret.add(n)
		m *= n
	return (ret, m)

def f2_rank(rows):
	rank = 0
	while rows:
		pivot_row = rows.pop()
		if pivot_row:
			rank += 1
			lsb = pivot_row & -pivot_row
			for (index, row) in enumerate(rows):
				if row & lsb:
					rows[index] = row ^ pivot_row
	return rank

def solve(a_values):
	ss = {}
	for a in a_values:
		(f, m) = factor(a)
		if f:
			ss[m] = f
	if not ss:
		return 1
	all_primes = set()
	for v in ss.values():
		all_primes.update(v)
	all_primes = sorted(all_primes)
	integers = []
	for item in ss.values():
		x = 0
		for (i, p) in enumerate(all_primes):
			if p in item:
				x += 1 << i
		integers.append(x)
	n = len(integers)
	r = f2_rank(integers)
	return 1 << r
q = int(input())
for _ in range(q):
	_ = int(input())
	a_values = set(map(int, input().strip().split()))
	print(solve(a_values))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))


from itertools import *
import sys

def print_mat(A):
	print('\n'.join((''.join(map(str, row)) for row in A)))

def e_sieve(n):
	sieve = [True] * (n + 1)
	sieve[0] = sieve[1] = False
	falses = [False] * (n // 2)
	curr = 2
	while curr * curr <= n:
		sieve[curr * 2::curr] = falses[:n // curr - 1]
		curr += 1
		while not sieve[curr]:
			curr += 1
	return [x for x in range(n) if sieve[x]]
primes = e_sieve(4000)

def factorize(n):
	d = list()
	for p in primes:
		if p * p > n:
			break
		power = 0
		while n % p == 0:
			power += 1
			n //= p
		if power % 2 == 1:
			d.append(p)
		if n == 1:
			break
	if n > 1:
		d.append(n)
	return d

def gauss_jordan(A, debug=False):
	(n, m) = (len(A), len(A[0]))
	(pivot_row, pivot_col) = (0, 0)
	while pivot_row < n and pivot_col < m:
		i_max = None
		for i in range(pivot_row, n):
			if A[i][pivot_col] == 1:
				i_max = i
				break
		if i_max is None:
			pivot_col += 1
			continue
		else:
			if pivot_row != i_max:
				if debug:
					print('Swapping row %d and %d' % (pivot_row, i_max))
				(A[pivot_row], A[i_max]) = (A[i_max], A[pivot_row])
				if debug:
					print_mat(A)
			for i in range(pivot_row + 1, n):
				if A[i][pivot_col] == 1:
					if debug:
						print('Adding row %d to row %d' % (pivot_row, i))
					for j in range(pivot_row, m):
						A[i][j] ^= A[pivot_row][j]
					if debug:
						print_mat(A)
			pivot_row += 1
			pivot_col += 1

def solve(A):
	A = [number for number in map(factorize, A) if number]
	if not A:
		return 0
	all_factors = set((x for number in A for x in number))
	prime_dict = {prime: rank for (rank, prime) in enumerate(all_factors)}
	matrix = [[0] * len(A) for _ in range(len(prime_dict))]
	for (i, number) in enumerate(A):
		for prime in number:
			matrix[prime_dict[prime]][i] = 1
	gauss_jordan(matrix)
	return sum((any((x > 0 for x in row)) for row in matrix))

def all_matrices(n, m):
	for lists in product([0, 1], repeat=n * m):
		yield [list(lists[i * m:(i + 1) * m]) for i in range(n)]
T = int(sys.stdin.readline())
for caseno in range(T):
	N = int(sys.stdin.readline())
	A = map(int, sys.stdin.readline().split())
	print(2 ** solve(A))