#include <bits/stdc++.h>
    #define lpa(i, a, b) for (signed i = a; i < b; ++i)
    #define lp(i, n) lpa(i, 0, n)
    #define fi first
    #define se second
    #define mkp make_pair
    #define pb push_back
    #define all(x) (x).begin(), (x).end()
    #define print(v)                                                               \
      lp(i, v.size()) cout << v[i] << ' ';                                         \
      cout << endl;
    typedef long long ll;
    using namespace std;
    template <typename T> using pr = pair<T, T>;
    // const ll mod = 998244353;
    const ll mod = 1e9 + 7;
    const int MAX = 1e6 + 1;
    vector<int> smp(MAX);
    // const int nmax = 1e5 + 1;
     
     
    void solve() {  
      int n, q; cin>>n;
      vector<int> a(n);
      map<int, vector<int>> sh;
      lp(i, n) {
        cin>>a[i];
        int x = 1, y = a[i];
        while (a[i] > 1) {
          int fc = smp[a[i]], cnt = 0;
          while (a[i] % fc == 0) a[i] /= fc, ++cnt;
          if (cnt%2) x *= fc; 
        }
        sh[x].push_back(y);
      }
      int max_len_sh = 0, sec = 0;
      for (auto it: sh) {
        max_len_sh = max(max_len_sh, (int)it.second.size());
        if (it.first == 1) sec += it.second.size();
        else if (it.second.size() % 2 == 0) sec += it.second.size();
      }
      cin>>q;
      lp(a, q) {
        ll w; cin>>w;
        if (w == 0) {
          cout << max_len_sh << endl;
        } else {
          cout << max(max_len_sh, sec) << endl;
        }
      }
    }
     
    signed main() {
      lp(i, MAX) smp[i] = i;
      for (int i = 2; i * i <= MAX; ++i) {
        if (smp[i] == i) {
          for (int j = i*i; j <= MAX; j += i)
            if (smp[j] == j) smp[j] = i;
        }
      }
ios_base::sync_with_stdio(false);
  cin.tie(NULL);
      signed t = 1;
      cin >> t;
      while (t--)
        solve();
    }