#include <bits/stdc++.h>
#define int long long
using namespace std;
int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}
#define MOD 1000000007
//const int MOD = 1e9 + 7;
int t, n, xt, a[601], dp[2][601][601], now;
int qpfyz(int x)
{
    for (int i = 2; i * i <= x; ++i)
    {
        while (!(x % (i * i)))
        {
            x /= (i * i);
        }
    }
    return x;
}
signed main()
{
    t = read();
    while (t--)
    {
        memset(dp, 0, sizeof(dp));
        dp[0][0][0] = 1;
        xt = 0;
        now = 0;
        n = read();
        for (int i = 1; i <= n; ++i)
        {
            a[i] = read();
            a[i] = qpfyz(a[i]);
        }
        sort(a + 1, a + n + 1);
        for (int i = 1; i <= n; ++i)
        {
            if (a[i] != a[i - 1])
            {
                for (int j = 0; j <= i; j++)
                {
                    for (int k = 1; k <= xt; k++)
                    {
                        dp[now ^ 1][j][0] = (dp[now ^ 1][j][0] + dp[now ^ 1][j][k] % MOD) % MOD;
                        dp[now ^ 1][j][k] = 0;
                    }
                }
                xt = 0;
            }
            for (int j = 0; j <= i; j++)
            {
                for (int k = 0; k <= min(xt, j); k++)
                {
                    if (j && k)
                        dp[now][j][k] = (dp[now][j][k] + (dp[now ^ 1][j - 1][k - 1] * (2 * xt - k + 1) % MOD)) % MOD;
                    dp[now][j][k] = (dp[now][j][k] + (dp[now ^ 1][j + 1][k] * (j - k + 1) % MOD)) % MOD;
                    dp[now][j][k] = (dp[now][j][k] + (dp[now ^ 1][j][k] * (i - 2 * xt + 2 *k -j ) % MOD)) % MOD;
                }
            }
            xt++;
            now ^= 1;
            memset(dp[now], 0, sizeof(dp[now]));
        }
        printf("%lld\n", dp[now ^ 1][0][0]);
    }
    return 0;
}