#include <bits/stdc++.h>
#define ll long long 
using namespace std;
const int inf = 1e9 + 7;
map<int, int>m;
int main()
{
	int t;
	scanf("%d", &t);
	while (t--) {
		m.clear();
		int n;
		scanf("%d", &n);
		int x;
		for (int i = 1; i <= n; i++) {
			scanf("%d", &x);
			for (int j = 2; j*j <= x; j++)
				while (x % (j*j) == 0)x /= (j*j);
			m[x]++;
		}
		int ans1 = 0,ans2=0,ansodd=0;
		for (auto e : m) 
		{
			ans1 = max(ans1, e.second);
			if (e.second & 1) 
			ansodd = max(ansodd, e.second); 
			else ans2 +=e.second;
		}
		if (m[1]&1)ans2 += m[1];
		ans2 = max(ans2, ansodd);
		ll q, w;
		scanf("%lld", &q);
		while (q--) {
			scanf("%lld", &w);
			if (w)printf("%d\n", ans2);
			else
				printf("%d\n", ans1);
		}
	}
	return 0;
}