#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define sc second
#define pb push_back
#define ll long long
#define trav(v,x) for(auto v:x)
using namespace std;
const int N = 1e6 + 100;

int n;
int a[N], tax[N], tnum = 0, cnt[N];

bool vis[N];

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	for(int i = 2; i * i <= 1000000; i++)
		tax[++tnum] = i * i;
	int tt;
	cin >> tt;
	vector<int>bin;
	while(tt--)
	{
		int ans = 0, tmp = 0;
		cin >> n;
		for(int i = 1; i <= n; i++)
		{
			int x;
			cin >> x;
			for(int j = 1; j <= tnum; j++)
			{
				while(x % tax[j] == 0) x /= tax[j];
			}
			cnt[x]++;
			bin.pb(x);
		}
		
		trav(v, bin)
		{
			if(vis[v])continue;
			ans = max(ans, cnt[v]);
			if(cnt[v] % 2 == 0 || v == 1)tmp += cnt[v];
			vis[v] = 1;
		}
		
		int tim;
		
		cin >> tim;
		
		while(tim--)
		{
			ll x;
			cin >> x;
			if(x == 0)cout << ans << '\n';
			else cout << max(ans, tmp) << '\n';
		}
		
		trav(v, bin)
			cnt[v] = 0, vis[v] = 0;
		bin.clear();
	}
	return 0;
}

