分石头

#include <iostream>
#include <unordered_set>
const int oxis = 1000001;
int primes[oxis], nprime;
bool notprime[oxis];
int fac[oxis];

int sg(int x)
{
	if (x == 1 || x == 2)
		return 1;
	if (!notprime[x])
		return 2;
	static int cache[oxis];
	if (cache[x])
		return cache[x];
	std::unordered_set<int> tui;
	int x2 = x / (x & (-x));		// 跳过因数 2
	for (int k = fac[x2]; x2 > 1; x2 /= k, k = fac[x2])
		tui.insert(sg(x / k));
	for (int i = 1;; ++i)
		if (tui.count(i) == 0)
			return cache[x] = i;
}

int main()
{
	int t;
	std::cin >> t;
	for (int i = 2; i < oxis; ++i) {
		if (!notprime[i]) {
			primes[nprime++] = i;
			fac[i] = i;
		}
		for (int j = 0, now; j < nprime && (now = i * primes[j]) < oxis; ++j) {
			notprime[now] = true;
			fac[now] = primes[j];
			if (i % primes[j] == 0)
				break;
		}
	}
	while (t--) {
		int n, ans = 0;
		std::cin >> n;
		while (n--) {
			int ni;
			std::cin >> ni;
			ans ^= sg(ni);
		}
		std::cout << !!ans << std::endl;
	}
}