#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll mod=1e9+7;
ll parent[1000005],rank1[1000005];
ll findRoot(ll curr)
{
    if(curr==parent[curr])
        return curr;
    return (parent[curr]=findRoot(parent[curr]));
}

void union1(ll x,ll y)
{
    ll rt1=findRoot(x);
    ll rt2=findRoot(y);
    if(rt1==rt2)
        return ;
    if(rank1[rt1]<rank1[rt2])
        parent[rt1]=rt2;
    else if(rank1[rt1]>rank1[rt2])
        parent[rt2]=rt1;
    else
    {
        parent[rt2]=rt1;
        rank1[rt1]++;

    }

}
int main(void)
{
    ll t;
    cin>>t;
    vector<ll> arr[1000005];

    bool prime[1000005];
    memset(prime,true,sizeof(prime));
    for(ll i=2;i<=1000003;i++)
    {
        if(prime[i])
        {
            arr[i].push_back(i);
            for(ll j=2*i;j<=1000002;j+=i)
                arr[j].push_back(i),prime[j]=false;

        }
    }
    
   // cout<<arr[6].size()<<endl;
    
    ll arr2[100005];
    while(t--)
    {

        for(ll i=1;i<=1000003;i++)
            parent[i]=i,rank1[i]=0;


        ll n;
        cin>>n;
        for(ll i=1;i<=n;i++)
        {
            cin>>arr2[i];
            ll x=arr2[i];
          //  cout<<x<<" dkhb "<<arr[arr2[i]].size()<<endl;
            for(ll i=1;i<arr[x].size();i++)
            {
                //cout<<arr[x][i-1]<<" "<<arr[x][i]<<endl;
                union1(arr[x][i-1],arr[x][i]);

            }
        }


        ll rts[100005];

        map<ll,ll> cnt;
        ll cnt1=0;
        for(ll i=1;i<=n;i++)
        {
            if(arr2[i]==1)
                cnt1++;
            else
            {
                
                rts[i]=findRoot(arr[arr2[i]][0]);
                cnt[rts[i]];
            }

            

        }


        ll x=cnt.size()+cnt1;
        ll res=1;
       // cout<<x<<endl;
        for(ll i=1;i<=x;i++)
            res=(res*2)%mod;

        res=(res-2+mod)%mod;

        cout<<res<<endl;




    }
    
    return 0;
}