#include <iostream> #include <stdio.h> #include <vector> #include <cstring> #define FOR(i,a,b) for (int i=(a); i<=(b); ++i) #define FORR(i,a,b) for (int i=(a); i>=(b); --i) #define REP(i,b) for (int i=0; i<(b); ++i) #define input stdin #define output stdout #define assign freopen #define endl '\n' #define sz(x) (int) x.size() #define div / #define mod % #define fillchar(x,y,z) memset(x,z,y) #define pii pair<int,int> #define fi first #define se second #define mp make_pair #define sqr(x) ((x)*(x)) #define read(x) x=ReadInt() typedef long long int64; typedef unsigned long long qword; typedef void procedure; using namespace std; int ReadInt() { char c; for (c = getchar(); c < '0' || c > '9'; c = getchar()); int ans = c - '0'; for (c = getchar(); c >= '0' && c <= '9'; c = getchar()) ans = ans * 10 + c - '0'; return ans; } void WriteInt(int64 x) { if (x > 9) WriteInt(x / 10); putchar(x % 10 + '0'); } const int maxn=1e6+5; const int base=1e9+7; int n,cnt1; int cnt[maxn]; vector<int> adj[maxn],fac[maxn]; bool able[maxn],vs[maxn]; int f[maxn],a[maxn]; procedure Input() { read(n); FOR(i,1,n) { read(a[i]); ++cnt[a[i]]; } cnt1=cnt[1]; cnt[1]=0; n=0; FOR(i,2,1000000) if (cnt[i]) a[++n]=i,cnt[i]=0; } procedure meo(int x) { int n=x,tmp; while (x>1) { adj[f[x]].push_back(n); fac[n].push_back(f[x]); tmp=f[x]; while (x mod tmp==0) { x/=f[x]; } } } procedure DFS(int u) { able[u]=false; for (int v:fac[u]) { if (!vs[v]) continue; vs[v]=false; for (int vv:adj[v]) if (able[vv]) DFS(vv); } } procedure Solve() { FOR(i,1,1000000) { fac[i].clear();adj[i].clear(); able[i]=true; vs[i]=true; } FOR(i,1,n) meo(a[i]); FOR(i,1,n) if (able[a[i]]) { ++cnt1; DFS(a[i]); } int64 res=1; FOR(i,1,cnt1) res=res*2 mod base; res-=2; res+=base; res= res mod base; if (cnt1==0) res=0; WriteInt(res); putchar('\n'); } procedure Init() { fillchar(f,sizeof(f),127); for (int i=2; i<=1000; ++i) if (f[i]==f[0]) for (int j=i*i; j<=1e6; j+=i) f[j]=min(f[j],i); FOR(i,2,1000000) if (f[i]==f[0]) f[i]=i; } int main() { #ifdef meomeomeooooo assign("input.txt","r",input); //assign("output.txt","w",output); #endif // meomeomeooooo Init(); int t; read(t); FOR(i,1,t) { Input(); Solve(); } return 0; }