#include <bits/stdc++.h>

using namespace std;

string ltrim(const string &);
string rtrim(const string &);
vector<string> split(const string &);

vector<int> sieve() {
    const int MX = 1e6;
    vector<bool> isprime(MX + 1, true);
    isprime[0] = false;
    isprime[1] = false;
    
    for(int i = 2; i*i <= MX; i++) {
        if(!isprime[i]) continue;
        for(int j = i*i; j <= MX; j += i) {
            isprime[j] = false;
        }
    }
    vector<int> primes;
    primes.reserve(count(isprime.begin(), isprime.end(), true));
    for(int i = 2; i <= MX; i++) {
        if(isprime[i]) {
            primes.push_back(i);
        }
    }
    return primes;
}

// Complete the solve function below.
int solve(vector<int> a) {
    const int MX = 1e6;
    
    int n = a.size();
    auto primes = sieve();
    vector<vector<int>> graph(MX+1, vector<int>());
    vector<bool> vis(MX+1, false);
    vector<bool> exists(MX+1, false);
    
    for(int x : a) {
        vector<int> pp;
        int y = x;
        for(int j = 0; j < (int)primes.size() && primes[j]*primes[j] <= x; j++) {
            if(y % primes[j]) continue;
            pp.push_back(primes[j]);
            while(y % primes[j] == 0) {
                y /= primes[j];
            }
        }
        if(y > 1) pp.push_back(y);
        
        for(int j = 0; j+1 < (int)pp.size(); j++) {
            graph[pp[j]].push_back(pp[j+1]);
            graph[pp[j+1]].push_back(pp[j]);
        }
        for(int p : pp) {
            exists[p] = true;
        }
    }
    int cnt = count(a.begin(), a.end(), 1);
    for(int p : primes) {
        if(vis[p] || !exists[p]) continue;
        cnt++;
        queue<int> q; q.push(p);
        vis[p] = true;
        while(!q.empty()) {
            int u = q.front(); q.pop();
            for(int v : graph[u]) {
                if(!vis[v]) {
                    vis[v] = true;
                    q.push(v);
                }
            }
        }
    }
    
    const long long MOD = 1e9 + 7;
    long long res = 1;
    for(int i = 0; i < cnt; i++) {
        res = res*2 % MOD;
    }
    res = (res - 2 + MOD) % MOD;
    return int(res);
}

int main()
{
    ofstream fout(getenv("OUTPUT_PATH"));

    string t_temp;
    getline(cin, t_temp);

    int t = stoi(ltrim(rtrim(t_temp)));

    for (int t_itr = 0; t_itr < t; t_itr++) {
        string a_count_temp;
        getline(cin, a_count_temp);

        int a_count = stoi(ltrim(rtrim(a_count_temp)));

        string a_temp_temp;
        getline(cin, a_temp_temp);

        vector<string> a_temp = split(rtrim(a_temp_temp));

        vector<int> a(a_count);

        for (int i = 0; i < a_count; i++) {
            int a_item = stoi(a_temp[i]);

            a[i] = a_item;
        }

        int result = solve(a);

        fout << result << "\n";
    }

    fout.close();

    return 0;
}

string ltrim(const string &str) {
    string s(str);

    s.erase(
        s.begin(),
        find_if(s.begin(), s.end(), not1(ptr_fun<int, int>(isspace)))
    );

    return s;
}

string rtrim(const string &str) {
    string s(str);

    s.erase(
        find_if(s.rbegin(), s.rend(), not1(ptr_fun<int, int>(isspace))).base(),
        s.end()
    );

    return s;
}

vector<string> split(const string &str) {
    vector<string> tokens;

    string::size_type start = 0;
    string::size_type end = 0;

    while ((end = str.find(" ", start)) != string::npos) {
        tokens.push_back(str.substr(start, end - start));

        start = end + 1;
    }

    tokens.push_back(str.substr(start));

    return tokens;
}