#include<bits/stdc++.h> #define ll long long #define fi first #define se second #define pb push_back #define pob pop_back #define W while #define fn(i,x) for(int i=0;i<x;i++) #define fs(i,s,x) for(int i=s;i<x;i++) #define fr(i,x) for(int i=x;i>=0;i--) #define fit(it,s) for(auto it=s.begin();it!=s.end();it++) #define mp make_pair #define pii pair<int,int> #define pll pair<ll,ll> #define vii vector<int> #define vll vector<ll> #define mod 1000000007 #define MAX 100005 using namespace std; ll modpower(ll x,ll y) { int res = 1; x = x % mod; while (y > 0) { if (y & 1) res = (res*x) % mod; y = y>>1; x = (x*x) % mod; } return res; } ll root(ll arr[],ll i) { while(arr[i]!=i) { arr[i]=arr[arr[i]]; i=arr[i]; } return i; } void dsuinit(ll arr[],ll siz[],ll n) { fn(i,n) { arr[i]=i; siz[i]=1; } } void unions(ll arr[],ll siz[],ll a,ll b) { ll root_a=root(arr,a); ll root_b=root(arr,b); if(siz[root_a]<siz[root_b]) { arr[root_a]=root_b; siz[root_b]+=siz[root_a]; } else { arr[root_b]=root_a; siz[root_a]+=siz[root_b]; } } ll submod(ll a,ll b) { return (a%mod - b%mod+ mod)%mod; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int t; cin>>t; W(t--) { ll n; cin>>n; ll s[n]={0},a[n]; dsuinit(a,s,n); ll b[n]; fn(i,n) cin>>b[i]; for(int i=0;i<n;i++) { for(int j=i+1;j<n;j++) { if(__gcd(b[i],b[j])!=1) { // cout<<"cds"; if(root(a,i)!=root(a,j)) unions(a,s,i,j); } } } set<ll> co; for(int i=0;i<n;i++) { // cout<<a[i]<<" "; co.insert(a[i]); } //cout<<"\n"; cout<<submod(modpower(2,co.size()),2)<<"\n"; } return 0; }