#include <cstdio>
#include <cstring>
const int N=105;
int T,n;
int a[N];
int mat[N][N];
bool prime[N*N];
int List[N*N];

void init(){
    int i,j;
    memset(prime,true,sizeof(prime));
    for (i=2;i<=10000;i++)
      for (j=i+i;j<=10000;j+=i)
        prime[j]=false;
    int cnt=0;
    for (i=2;i<=10000;i++)
      if (prime[i]) List[++cnt]=i;
}

int Num[65];

void output(int cf){
    memset(Num,0,sizeof(Num));
    Num[0]=1;
    for (int k=1;k<=cf;k++){
        for (int i=0;i<60;i++) Num[i]*=2;
        for (int i=0;i<60;i++){
            Num[i+1]+=Num[i]/10;
            Num[i]%=10;
        }
    }
    Num[0]--;
    for (int i=0;Num[i]<0;i++){
        Num[i]+=10;
        Num[i+1]--;
    }
    int i;
    for (i=60;i>=1;i--) if (Num[i]!=0) break;
    for (;i>=0;i--) printf("%d",Num[i]);
    puts("");
}

template <class T> inline void swap(T &x,T &y){ T tmp=x; x=y; y=tmp; }

void solve(){
    int cut,i,j,k,now=1;   //now表示当前主元
    cut=1;
    while (now<=n && cut<=T){
        bool check=false;
        while (now<=n && cut<=T && !check){
            for (i=cut;i<=T;i++)
              if (mat[i][now]){
                  check=true;
                  k=i;
                  break;
              }
            if (check){
                for (j=1;j<=n;j++)
                  swap(mat[k][j],mat[cut][j]);
                for (i=cut+1;i<=T;i++)
                  if (mat[i][now])
                    for (j=now;j<=n;j++)
                      mat[i][j]^=mat[cut][j];
                cut++;
            }
            now++;
        }
    }
    cut--;
    output(n-cut);
}

int main(){
    init();
    int Tc,i,j;
    for (scanf("%d",&Tc);Tc;Tc--){
        scanf("%d%d",&T,&n);
        memset(mat,0,sizeof(mat));
        for (i=1;i<=n;i++){
          scanf("%d",&a[i]);
          for (j=1;j<=T;j++)
            if (a[i]%List[j]==0){
                int tmp=a[i],cnt=0;
                while (tmp%List[j]==0){tmp/=List[j]; cnt++;}
                if (cnt&1) mat[j][i]=1;
            }
        }
        solve();
        if (Tc>1) puts("");
    }
}