#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int n,a[maxn],sat[maxn];
bool check[maxn];
void SNT()
{
    memset(check,1,sizeof check);
    check[1] = 0;
    for (int i = 2; i*i < maxn; ++i)
        if (check[i])
            for (int j = i*i;j < maxn;j+=i)
            {
                check[j] = false;
                sat[j] = i;
            }
    for (int i = 2;i < maxn; i++)
        if (check[i])
            sat[i] = i;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    #ifdef TLH2203
        freopen("1470B.inp","r",stdin);
        freopen("1470B.out","w",stdout);
    #endif // TLH2203
    SNT();
    int t;
    cin >> t;
    while(t--)
    {
        cin >> n;
        for (int i = 1; i <= n; ++i)
        {
            cin >> a[i];
            int tmp = 1,dem;
            while(a[i]>1)
            {
                dem = 0;
                int res = sat[a[i]];
                while(a[i] % res == 0)
                {
                    a[i] /= res;
                    ++dem;
                }
                if (dem&1)
                    tmp*=res;
            }
            a[i] = tmp;
        }
        a[n+1] = 0;
        sort(a + 1,a + n + 1);
        int ans = 0, dem = 1, maxx = 0, tong = 0;
        for (int i = 1; i <= n; i++)
            if (a[i] == a[i+1])
                dem++;
            else
            {
                if (dem % 2 == 1 && a[i] > 1)
                    ans = max(ans, dem);
                else tong += dem;
                maxx=max(maxx,dem);
                dem = 1;
            }
        int q;
        cin>>q;
        while(q--)
        {
            long long w;
            cin >> w;
            if (w == 0)
            {
                cout << maxx << '\n';
                continue;
            }
            cout << max(ans,tong) << '\n';
        }
    }
}

