#include<iostream>
#include<cstdio>
#include<vector>
#include<cmath>
using namespace std;
const int maxn=4e5,mod=998244353;
int T,n;
int a[maxn],Cnt[maxn],cnt[maxn];
int base[maxn][30],siz[maxn];
long long po[maxn],fac[maxn],inv[maxn],Ans;
long long qpow(long long x,int n){
    long long ret=1;
    while(n){
        if(n&1){ret=ret*x%mod;}
        x=x*x%mod;
        n>>=1;
    }
    return ret;
}
void Add(int num,int x){
    for(int i=20;i>=0;i--){
        if(x&(1<<i)){
            if(base[num][i]){
                x^=base[num][i];
            }
            else{
                siz[num]++;
                base[num][i]=x;
                return;
            }
        }
    }
    return;
}
void Merge(int a,int b,int c){//a,b合并到c
    if(siz[a]<siz[b]) swap(a,b);
    siz[0]=siz[a];
    for(int i=0;i<=20;i++){
        base[0][i]=base[a][i];
    }
    for(int i=0;i<20;i++){
        if(base[b][i]){
            Add(0,base[b][i]);
        }
    }
    siz[c]=siz[0];
    for(int i=0;i<=20;i++){
        base[c][i]=base[0][i];
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    po[0]=1;
    for(int i=1;i<=200000;i++){
        po[i]=po[i-1]*2%mod;
    }
    fac[0]=1;
    for(int i=1;i<=200000;i++){
        fac[i]=fac[i-1]*i%mod;
    }
    inv[200000]=qpow(fac[200000],mod-2);
    for(int i=200000;i>=1;i--){
        inv[i-1]=inv[i]*i%mod;
    }
    cin>>T;
    while(T--){
        cin>>n;
        for(int i=1;i<=n;i++){
            cnt[i]=0;
            Cnt[i]=0;
            siz[i]=0;
            for(int j=0;j<=20;j++){
                base[i][j]=0;
            }
        }
        siz[0]=0;
        for(int i=0;i<=20;i++){
            base[0][i]=0;
        }
        for(int i=1;i<=n;i++){
            cin>>a[i];
            cnt[a[i]]++;
            Add(0,a[i]);
        }
        Ans=(po[n-siz[0]]-1);
        for(int i=1;i<=n;i++){
            for(int j=i;j<=n;j+=i){
                Cnt[j]+=cnt[i];
            }
        }
        for(int i=1;i<=n;i++){
            int cur=i;
            siz[i]=siz[1];
            for(int j=0;j<=20;j++){base[i][j]=base[1][j];}
            for(int j=2;j<=sqrt(i);j++){
                if(cur%j==0){
                    Merge(i,i/j,i);
                }
                while(cur%j==0){
                    cur/=j;
                }
            }
            long long C=0;
            for(int j=1;j<=cnt[i];j+=2){
                C=(C+fac[cnt[i]]*inv[j]%mod*inv[cnt[i]-j]%mod)%mod;
            }
            Ans=(Ans+1ll*C*po[Cnt[i]-cnt[i]-siz[i]])%mod;
            if(cnt[i]){
                Add(i,i);
            }
        }
        printf("%lld\n",Ans);
    }
    system("pause");
    return 0;
}