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

const int A = 1000005;
int isprime[A], red[A]; // red[i] = reduced value of i

void get_red() {
    for (int i = 0; i < A; i++) isprime[i] = red[i] = 1;
    
    for (int i = 2; i < A; i++) {
        if (isprime[i]) {
            red[i] = i;
            
            for (int j = i + i; j < A; j += i) {
                isprime[j] = 0;
                
                int e = 0, V = j;
                while (V % i == 0) {
                    ++e;
                    V /= i;
                }
                
                if (e & 1) red[j] *= i;
            }
        }
    }
}

const int N = 300005;
int a[N];

int main() {
    get_red();
    
    int tc; scanf("%d", &tc);
    while (tc--) {
        int n; scanf("%d", &n);
        for (int i = 0; i < n; i++) scanf("%d", &a[i]);
        a[n] = -1;
        
        vector<int> vals;
        for (int i = 0; i < n; i++) a[i] = red[a[i]];
        sort(a, a + n);
        
        int odd = 0, even = 0, mx = 0;
        
        int cur = 1;
        for (int i = 1; i <= n; i++) {
            if (a[i] == a[i - 1]) ++cur;
            else {
                mx = max(mx, cur);
                
                if (a[i - 1] == 1) {
                    even += cur;
                }
                else {
                    if (cur & 1) odd = max(odd, cur);
                    else even += cur;
                }
                
                cur = 1;
            }
        }
        
        int q; scanf("%d", &q);
        while (q--) {
            long long w; scanf("%lld", &w);
            
            if (w) printf("%d\n", max(odd, even));
            else printf("%d\n", mx);
        }
    }
    
    return 0;
}