SPLIT

#define NguyenDangQuan the_author
#define my_heart love_you_to_the_moon_and_back

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

bool typetest;
inline void fastIOfileinput(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    typetest = 1;
}

const int N = 1e6 + 1;
vector<int> ad[N], have[N], adj[N];
int n, a[N];
bool ok[N];
/// Ethoras
void Prepare(){
    vector<bool> ck(N);
    for(int i = 2; i < N; ++i)
        if(!ck[i]){
            for(int j = i; j < N; j += i)
                ck[j] = 1,
                ad[j].push_back(i);
        }
}

void Read(){
    for(int i = 1; i < N; ++i)
        have[i].clear();
    cin >> n;
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
        ok[i] = 0;
        adj[i].clear();
                /// Duyệt các ước nguyên tố của a[i]
        for(auto j : ad[a[i]]){
                        ///nếu tồn tại ít nhất 1 đỉnh thì ta nối nó vào
            if(have[j].size())
                adj[i].push_back(have[j][0]),
                adj[have[j][0]].push_back(i);
                        /// thêm đỉnh này vào thành phần liên thông
            have[j].push_back(i);
        }
    }
}

const ll mod = 1e9 + 7;

void dfs(int v){
    ok[v] = 1;
    for(auto i : adj[v])
        if(!ok[i])
            dfs(i);
}

ll Pow(ll a, ll b){
    if(b == 0)
        return 1;
    ll t = Pow(a, b / 2);
    if(b & 1)
        return (t * t) % mod * a % mod;
    return t * t % mod;
}

void Solve(){
    ll ans = 0;
        /// Đếm liên thông
    for(int i = 1; i <= n; ++i)
        if(!ok[i]){
            ++ans;
            dfs(i);
        }
        ///Đáp án là (2^ans - 2)
    cout << ((Pow(2, ans) - 2ll) % mod + mod) % mod << "\n";
}

main(){
    fastIOfileinput();
    if(typetest){
        int t;
        cin >> t;
        Prepare();
        while(t--){
            Read();
            Solve();
        }
    }
    else{
        Read();
        Solve();
    }
}