#include<bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
const int N = 1000050;
int a[N], c[N], now[N], p[N], inv[N], mx[3][N];
bool vis[2][N], r[N];
vector<pair<int, int>> e[N];
vector<int> Prime, q;
inline int read() {
    int w = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9') {
        w = (w << 1) + (w << 3) + ch - 48;
        ch = getchar();
    }
    return w;
}
inline int Pow(int a, int b) {
    int ans = 1;
    for (; b; b >>= 1, a *= a) if (b & 1) ans *= a;
    return ans;
}
inline void Solve() {
    int n, lcm = 1, ans = 0;
    n = read();
    for (int i = 1; i <= n; i++) a[i] = read(), r[i] = 0;
    for (int i = 1; i <= n; i++) {
        if (r[i]) continue;
        int sz = 1; r[i] = 1;
        for (int p = a[i]; p != i; p = a[p]) sz++, r[p] = 1;
        q.push_back(sz); c[sz]++;
    }
    sort(q.begin(), q.end());
    q.erase(unique(q.begin(), q.end()), q.end());
    if ((int)q.size() == 1 && c[q[0]] == 1) {
        for (auto x : q) c[x] = 0;
        vector<int>().swap(q);
        printf("0\n");
        return ;
    }
    for (auto t : q) {
        int opt = t;
        while (opt > 1) {
            int P = p[opt], s = 0;
            while (opt % P == 0) opt /= P, s++;
            e[t].push_back({P, s});
            for (int  j = 0; j < c[t]; j++) 
                for (int cs = s, i = 0; i <= 2; i++)
                    if (mx[i][P] < cs) swap(mx[i][P], cs);
        }
    }
    for (auto P : Prime) {
        lcm = 1ll * lcm * Pow(P, mx[0][P]) % MOD;
        now[P] = mx[0][P];
    }
    auto Delete = [&](int x, int t) {
        if (!vis[0][x] && mx[0][x] == t) vis[0][x] = 1;
        else if (!vis[1][x] && mx[1][x] == t) vis[1][x] = 1;
    };
    for (auto i : q) {
        for (auto j : q) {
            if (i == j && c[i] == 1) continue;
            int res = lcm, opt = i + j;
            vector<int> h;
            for (auto [x, y] : e[i]) Delete(x, y), h.push_back(x);
            for (auto [x, y] : e[j]) Delete(x, y), h.push_back(x);
            sort(h.begin(), h.end());
            h.erase(unique(h.begin(), h.end()), h.end());
            for (auto P : h) {
                now[P] = 0;
                if (!vis[0][P]) now[P] = mx[0][P];
                else if (!vis[1][P]) now[P] = mx[1][P];
                else now[P] = mx[2][P];
                res = 1ll * res * inv[Pow(P, mx[0][P] - now[P])] % MOD;
            }
            while (opt > 1) {
                int P = p[opt], s = 0;
                while (opt % P == 0) opt /= P, s++;
                if (s > now[P]) res = 1ll * res * Pow(P, s - now[P]) % MOD;
            }
            if (i == j) ans += 1ll * res * c[i] % MOD * (c[i] - 1) % MOD * i % MOD * i % MOD;
            else ans += 1ll * res * c[i] % MOD * c[j] % MOD * i % MOD * j % MOD;
            ans %= MOD;
            for (auto P : h) {
                vis[0][P] = vis[1][P] = 0;
                now[P] = mx[0][P];
            }
        }
    }
    printf("%d\n", ans);
    for (auto x : q) 
        c[x] = 0, vector<pair<int, int>>().swap(e[x]);
    for (auto P : Prime) mx[0][P] = mx[1][P] = mx[2][P] = 0;
    vector<int>().swap(q);
}
signed main() {
    int T;
    T = read(); inv[1] = 1;
    for (int i = 2; i <= N - 5; i++) {
        inv[i] = MOD - 1ll * inv[MOD % i] * (MOD / i) % MOD;
        if (!p[i]) p[i] = i, Prime.push_back(i);
        for (auto P : Prime) {
            if (i * P > N - 5) break;
            p[i * P] = P;
            if (i % P == 0) break;
        }
    }
    while (T--) Solve();
    return 0;
}