#include <bits/stdc++.h>

using namespace std;

const int nmax = 2 * 1e6;
const int mod = 1e9 + 7;

int v[nmax + 1];

bool viz[nmax + 1];
vector<int> g[nmax + 1];

void dfs (int nod) {
    viz[nod] = 1;

    for (auto i : g[nod]) {
        if (viz[i] == 0) {
            dfs(i);
        }
    }
}

int gcd (int a, int b) {
    while (b > 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(nullptr);

    int t;
    cin >> t;

    while (t --) {
        int n;
        cin >> n >> v[1];

        int d = v[1];

        for (int i = 2; i <= n; ++ i) {
            cin >> v[i];
            d = gcd(d, v[i]);
        }

        if (d != 1) {
            cout << "0\n";
        } else {
            for (int i = 1; i <= n; ++ i) {
                for (int j = 2; j * j <= v[i]; ++ j) {
                    if (v[i] % j == 0) {
                        g[i].push_back(j + n);
                        g[j + n].push_back(i);

                        while (v[i] % j == 0)
                            v[i] /= j;
                    }
                }

                if (v[i] != 1) {
                    g[i].push_back(v[i] + n);
                    g[v[i] + n].push_back(i);
                }
            }

            int ans = 1;
            for (int i = 1; i <= n; ++ i) {
                if (viz[i] == 0) {
                    ans = ans * 2 % mod;
                    dfs(i);
                }
            }

            ans -= 2;
            if (ans < 0)
                ans += mod;
            cout << ans << "\n";
        }

        for (int i = 1; i <= nmax; ++ i) {
            g[i].clear();
            viz[i] = 0;
        }
    }

    return 0;
}