#include <bits/stdc++.h>

#define int long long
#define all(x) x.begin(), x.end()
using namespace std;

const int mod1 = 1791791, mod2 = (int) 1e9 + 7;
const int x1 = 179, x2 = (int) 1e6 + 3;

vector<int> primes;

void is_prime(int n) {
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            return;
        }
    }
    primes.push_back(n);
}

bool used[1000500];
pair<int, int> kuku[1000500];

pair<int, int> factor(int n) {
    if (used[n]) {
        return kuku[n];
    }
    int n1 = n;
    map<int, int> now;
    int ind = 0;
    int k = primes[0];
    while (k * k <= n) {
        while (n % k == 0) {
            now[k]++;
            n /= k;
        }
        ind++;
        k = primes[ind];
    }
    if (n != 1) {
        now[n]++;
    }
    vector<int> res;
    for (auto el : now) {
        if (el.second % 2) {
            res.push_back(el.first);
        }
    }
    int h1 = 0, h2 = 0;
    for (int el : res) {
        h1 = (h1 * x1 + el) % mod1;
        h2 = (h2 * x2 + el) % mod2;
    }
    used[n1] = true;
    kuku[n1] = {h1, h2};
    return {h1, h2};
}

const int INF = (int) 1e15;

int mx_(vector<int> &a) {
    if (a.empty()) {
        return -INF;
    }
    return *max_element(all(a));
}

void sol() {
    int n;
    cin >> n;
    map<pair<int, int>, int> boba;
    for (int i = 0; i < n; i++) {
        int el;
        cin >> el;
        boba[factor(el)]++;
    }
    vector<int> odd, even;
    for (auto &el : boba) {
        if (el.first.first == 0 && el.first.second == 0) {
            even.push_back(el.second);
        } else if (el.second % 2) {
            odd.push_back(el.second);
        } else {
            even.push_back(el.second);
        }
    }
    int mxe = mx_(odd);
    int res0 = max(mxe, mx_(even));
    int sm = 0;
    for (int el : even) {
        sm += el;
    }
    int res1 = max(mxe, sm);
    int q;
    cin >> q;
    while (q--) {
        int w;
        cin >> w;
        cout << (w == 0 ? res0 : res1) << '\n';
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    for (int i = 2; i < 1050; i++) {
        is_prime(i);
    }
    int t = 1;
    cin >> t;
    while (t--) {
        sol();
    }
}