思维题。

看到 gcd 和 lcm 首先想到分解质因数。令 $a=\prod_{i=1}^{\infty}p_{i}^{e_{i}},b=\prod_{i=1}^{\infin}p_{i}^{e'_{i}}$（ $p_{i}$ 为第 $i$ 个质数）。则 $lcm(a,b)=\prod_{i=1}^{\infin}p_{i}^{\max(e_{i},e'_{i})},\gcd(a,b)=\prod_{i=1}^{\infin}p_{i}^{\min(e_{i},e'_{i})}$。令 $t=\frac{lcm(a,b)}{gcd(a,b)}$，则 $t=\prod_{i=1}^{\infin}p_{i}^{\max(e_{i},e'_{i})-\min(e_{i},e'_{i})}$。因此 $t$ 为完全平方数当且仅当 $\forall i\in \mathbb{N^{+}},2|(\max(e_{i},e'_{i})-\min(e_{i},e'_{i}))$。也就是 $e_{i}$ 与 $e'_{i}$ 奇偶性相同。因此 $a$ 和 $b$ 是否相邻就只与 $e_{i}$ 和 $e'_{i}$ 的奇偶性有关了，我们把奇数看做 $1$，偶数看做 $0$，每个数就可以用一个 $01$ 串来表示，而两个数相邻当且仅当它们的 $01$ 串相同。

这也就是说，每次变化都会将数组中所有 $01$ 串相同的元素合并在一起（其实就是把这些 $01$ 串加起来）。如果参与合并的元素个数为偶，那么合并过后每个 $e_{i}$ 都会变为 $0$，即一个全 $0$ 串。如果参与合并的元素个数为奇，那么合并之后每个元素的 $01$ 串并不会发生改变。这意味着数组在变化过一次后，出现的全 $0$ 串从此始终是全 $0$ 串，非全 $0$ 串从此也不会再发生改变，所以答案最多只有两种： $w=0$ 时，和 $w=1$ 时，直接套哈希模拟就行，由于 $01$ 串的哈希值只与 $1$ 的位置有关，因此我们可以把所有 $1$ 的位置拎出来做哈希。时间复杂度为 $O(n\log n+n\sqrt {\max a_{i})}$。

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define mod1 998244353
#define mod2 19260817
#define base1 19260813
#define base2 300007
#define ll long long
#define fo(i,x,y) for(register int i=x;i<=y;++i)
#define go(i,x,y) for(register int i=x;i>=y;--i)
using namespace std;

inline int read(){
    int x=0,fh=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-') fh=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    return x*fh;
}

const int N=1e6+5;
int np[N],p[N],top,rk[N];

void xxs(){
    fo(i,2,N-1){
        if(!np[i]) p[++top]=i,rk[i]=top;
        fo(j,1,top){
            int t=i*p[j];
            if(t>=N) break;
            np[t]=1;
            if(i%p[j]==0) break;
        }
    }
}

int a[N];

struct Ha{
    int v1,v2;
    bool operator<(const Ha &x){
        if(v1!=x.v1) return v1<x.v1;
        return v2<x.v2;
    }
    bool operator==(const Ha &x){return v1==x.v1&&v2==x.v2;} 
}hx[N];

void work(){
    int n=read();
    fo(i,1,n) a[i]=read();
    fo(i,1,n){
        hx[i].v1=hx[i].v2=0;
        int t=a[i];
        //printf("%d:\n",t);
        fo(j,1,top){
            if(p[j]*p[j]>t) break;
            bool cnt=0;
            while(t%p[j]==0){
                t/=p[j];
                cnt^=1;
            }
            //printf("%d %d\n",p[j],cnt);
            if(cnt) hx[i].v1=(1ll*hx[i].v1*base1+j)%mod1,hx[i].v2=(1ll*hx[i].v2*base2+j)%mod2;
        }
        if(t>1) hx[i].v1=(1ll*hx[i].v1*base1+rk[t])%mod1,hx[i].v2=(1ll*hx[i].v2*base2+rk[t])%mod2;
        //printf("v1=%d v2=%d\n",hx[i].v1,hx[i].v2);
    }
    sort(hx+1,hx+1+n);
    int ans0=0,ans1=0,cnt=0;
    fo(i,1,n){
        int pos=i;
        while(pos<=n&&hx[pos]==hx[i]) ++pos;
        int len=pos-i;
        //printf("%d:%d %d %d %d\n",i,hx[i].v1,hx[i].v2,pos,len);
        ans0=max(ans0,len);
        ans1=max(ans1,len);
        if(len%2==0||hx[i].v1+hx[i].v2==0) cnt+=len;
        i=pos-1;
    }
    ans1=max(ans1,cnt);
    int q=read();
    while(q--){
        ll w;
        scanf("%lld",&w);
        if(w==0) printf("%d\n",ans0);
        else printf("%d\n",ans1);
    }
    //puts("");
}

int main(){
    xxs();
    int T=read();
    while(T--){
        work();
    }
    return 0;
}