#include <bits/stdc++.h>
using namespace std;

#define int long long
#define cerr if(0)cerr


// RANDOM UTILITIES *********************************************************************

// rint: generate a random integer between lo and hi, inclusive
//   -> O(1)
// rreal: generate a random real number between lo and hi, inclusive
//   -> O(1)

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

template<class T>
T rint(T lo,T hi){return uniform_int_distribution<T>(lo,hi)(rng);}
template<class T>
T rreal(T lo,T hi){return uniform_real_distribution<T>(lo,hi)(rng);}

// **************************************************************************************

int P1,P2;
const int M1=1000000123,M2=1000000321;

const int N=1e6+69;
vector<int> sv(N,-1);

pair<int,int> factorize(int x){
	cerr<<"call factorize x="<<x<<"\n";
	map<int,int> mp;
	while(sv[x]!=-1){
		mp[sv[x]]++;
		cerr<<"  cut "<<sv[x]<<"\n";
		x/=sv[x];
	}
	if(x!=1)mp[x]++;
	vector<int> good;
	for(auto [key,val]:mp){
		if(val&1)good.push_back(key);
	}
	pair<int,int> ret;
	int pp1=1,pp2=1;
	for(int i=0;i<(int)good.size();i++){
		ret.first+=good[i]*pp1;
		ret.first%=M1;
		ret.second+=good[i]*pp2;
		ret.first%=M2;
		pp1*=P1;pp1%=M1;
		pp2*=P2;pp2%=M2;
	}
	return ret;
}

void solve(){
	int n;cin>>n;
	vector<int> a(n);
	for(int &x:a)cin>>x;
	map<pair<int,int>,int> ct;
	for(int x:a){
		ct[factorize(x)]++;
	}
	int t0=0,t1=0,z=0;
	vector<int> v;
	for(auto [key,val]:ct){
		t0=max(t0,val);
		if(val%2==0||(key.first==0&&key.second==0))z+=val;
		else v.push_back(val);
	}
	v.push_back(z);
	cerr<<"z is "<<z<<"\n";
	t1=*max_element(v.begin(),v.end());
	int q;cin>>q;
	while(q--){
		int w;cin>>w;
		if(w==0)cout<<t0<<"\n";
		else cout<<t1<<"\n";
	}
}

signed main(){
	cin.tie(nullptr)->sync_with_stdio(false);
	sv[1]=-1;
	for(int i=2;i<N;i++){
		if(sv[i]!=-1)continue;
		for(int j=i+i;j<N;j+=i){
			sv[j]=i;
		}
	}
	int t;cin>>t;
	while(t--){
		P1=rint(1000000,10000000);P2=rint(1000000,10000000);
		if(P1%2==0)P1++;
		if(P2%2==0)P2++;
		solve();
	}	
}
