#include <bits/stdc++.h>

using namespace std;

const int max_size = 1000000 + 5;

int p[max_size];
map<int, int> mp;
int primes[max_size];

void pre() {
    for (long long i = 1; i <= 1e6; i++) p[i] = i;
    for (long long i = 2; i <= 1e6; i++) {
        if (primes[i] == 0) {
            for (long long j = 2 * i; j <= 1e6; j += i) {
                primes[j] = 1;
                while (p[j] % (i * i) == 0) {
                    p[j] /= (i * i);
                }
            }
        }
    }
}


int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    int t;
    //cin >> t;
    pre();


    cin >> t;
    for (int l = 0; l < t; ++l) {
        int n, q;
        cin >> n;
        for (int i = 0; i < n; ++i) {
            int x;
            cin >> x;
            mp[p[x]]++;
        }


        cin >> q;
        int maxi_group = 0, sum = 0;

        for (auto el : mp) {
            //cout << " group: " << el.first << " col: " << el.second << "\n";
            if (el.first != 1 && el.second % 2 == 0) {
                sum += el.second;
            }
            maxi_group = max(el.second, maxi_group);
        }

        for (int i = 0; i < q; ++i) {
            long long w;
            cin >> w;
            if (w == 0) {
                cout << maxi_group << "\n";
            }
            else {
                cout << max(maxi_group, sum + mp[1]) << "\n";
            }
        }
        mp.clear();
    }

    return 0;
}
