#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 600 + 5;
const int inf = 1e5;
const long long mod = 1e9 + 7;
int cnt, prime[inf];
bool vis[inf + 5];
long long C[maxn][maxn];
void init() {
    for (int i = 2; i <= inf; i++) {
        if (!vis[i]) prime[++cnt] = i;
        for (int j = 1; j <= cnt && i * prime[j] <= inf; j++) {
            vis[i * prime[j]] = true;
            if (i % prime[j] == 0) break;
        }
    }
    C[0][0] = 1;
    for (int i = 1; i <= 600; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
    }
}
bool check(int x, int y) {
    for (int i = 1; i <= cnt; i++) {
        int cnt1 = 0, cnt2 = 0;
        for (; x % prime[i] == 0; cnt1++) x /= prime[i];
        for (; y % prime[i] == 0; cnt2++) y /= prime[i];
        if ((cnt1 + cnt2) & 1) return false;
    }
    return x == y;
}
int T, n, m;
int a[maxn], b[maxn], num[maxn], sum[maxn];
long long f[1 << 20][20], g[maxn][maxn];
int main() {
    init();
    scanf("%d", &T);
    while (T--) {
        m = 0;
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            scanf("%d", a + i);
            int j = 1;
            for (; j <= m; j++) {
                if (check(a[i], b[j])) {
                    num[j]++;
                    break;
                }
            }
            if (j > m) b[++m] = a[i], num[m] = 1;
            a[i] = j;
        }
        long long ans = 0;
        if (n <= 18) {
            memset(f, 0, sizeof(f));
            for (int i = 0; i < n; i++) f[1 << i][i] = 1;
            for (int i = 1; i < (1 << n); i++)
                for (int j = 0; j < n; j++)
                    if (((i >> j) & 1) ^ 1)
                        for (int k = 0; k < n; k++)
                            if ((i >> k) & 1 && a[j] != a[k])
                                f[i | (1 << j)][j] = (f[i | (1 << j)][j] + f[i][k]) % mod;
            for (int i = 0; i < n; i++) ans = (ans + f[(1 << n) - 1][i]) % mod;
        } 
        printf("%lld\n", ans);
    }
    return 0;
}