#include <bits/stdc++.h>
#include <algorithm>

using namespace std;

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

// Complete the solve function below.

void init(vector<int>& body, int n) {
    body.resize(n);
    for (int i = 0; i < n; ++ i) {
        body[i] = i;
    }
}

int get(vector<int>& body, int i) {
    return body[i] == i? i: body[i] = get(body, body[i]);
}

void merge(vector<int>& body, int i, int j) {
    if (rand() & 1) {
        body[get(body, i)] = get(body, j);
    } else {
        body[get(body, j)] = get(body, i);
    }
}

long long pow_mod(long long a, long long p, long long m) {
    if (p == 0)
        return 1 % m;
    if (p & 1)
        return pow_mod(a * a % m, p / 2, m) * a % m;
    else 
        return pow_mod(a * a % m, p / 2, m);
}

const long long mod = 1000000007;

int solve(const vector<int>& a) {

    vector<bool> is_prime(1000001, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 4; i < is_prime.size(); i += 2) {
        is_prime[i] = false;
    }
    for (int i = 3; i * i < is_prime.size(); i += 2) {
        if (is_prime[i])
            for (int j = i * i; j < is_prime.size(); j += 2 * i) {
                is_prime[j] = false;
            }
    }
    vector<int> primes;
    for (int i = 0; i < is_prime.size(); ++ i)
        if (is_prime[i])
            primes.push_back(i);
    int n = a.size();
    int m = primes.size();
    vector<int> pg;
    init(pg, m);
    int os = 0;
    vector<bool> pf(m);
    for (int i = 0; i < n; ++ i) {
        if (a[i] == 1) {
            os++;
            continue;
        }
        vector<int> ps;
        int c = a[i];
        for (int j = 0; primes[j] * primes[j] <= c; ++ j) {
            if (c % primes[j] == 0) {
                ps.push_back(j);
            }
            while (c % primes[j] == 0) {
                c /= primes[j];
            }
        }
        if (c > 1) {
            ps.push_back(lower_bound(primes.begin(), primes.end(), c) - primes.begin());
        }
        int first = ps[0];
        for (int j = 0; j < ps.size(); ++ j) {
            merge(pg, first, ps[j]);
            pf[ps[j]] = true;
        }
    }
    set<int> gs;
    for (int i = 0; i < m; ++ i) 
        if (pf[i])
            gs.insert(get(pg, i));
    long long res = (pow_mod(2, gs.size() + os, mod) - 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;
}