#include<bits/stdc++.h>
using namespace std;
const int N=300010, M=1000010;
int t, n, q, a[N], cnt[M];
long long w;
int main(){
	scanf("%d", &t);
	while (t){
		t--;
		scanf("%d", &n);
		int ans1=0, ans2=0;
		for (int i=0; i<n; i++) {
			scanf("%d", a+i);
			for (int j=trunc(sqrt(a[i])); j>1; j--)
				if (a[i]%(j*j)==0){
					a[i]/=j*j;
					break;
				}
			cnt[a[i]]++;
			ans1=max(ans1,cnt[a[i]]);
		}
		ans2+=cnt[1];cnt[1]=0;
		for (int i=0; i<n; i++) {
			if ((cnt[a[i]] & 1)==0) {
				ans2+=cnt[a[i]];
				cnt[a[i]]=0;
			}
		}
		scanf("%d", &q);
		for (int i=0; i<q; i++){
			scanf("%lld", &w);
			printf("%d\n", (w==0?ans1:max(ans1,ans2)));
		}
		for (int i=0; i<n; i++) cnt[a[i]]=0;
	}
}