#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long ll;
const int mod = 1e9 + 9;
const int maxn = 100005;

ll fac[maxn], f[maxn];
int a[maxn];
bool vis[maxn];

ll qpow(ll x, ll n) {
    ll res = 1;
    while (n) {
        if (n & 1) res = (res * x) % mod;
        n >>= 1;
        x = (x * x) % mod;
    }
    return res;
}

void init() {
    fac[0] = 1;
    for (int i = 1; i < maxn; i++) {
        fac[i] = fac[i - 1] * i % mod;
    }
    f[1] = 1;
    for (int i = 2; i < maxn; i++) {
        f[i] = qpow(i, i - 2);
    }
}

int main() {
    init();
    int T;
    scanf("%d", &T);
    while (T--) {
        memset(vis, 0, sizeof(vis));
        int n;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
        }
        ll ans = 1;
        int circle_count = 0;
        for (int i = 1; i <= n; i++) {
            if (vis[i]) continue;
            int cnt = 1;
            int j = a[i];
            vis[i] = true;
            while (j != i) {
                vis[j] = true;
                j = a[j];
                cnt++;
            }
            circle_count++;
            ans = ans * f[cnt] % mod;
            ans = ans * qpow(fac[cnt - 1], mod - 2) % mod;
        }
        ans = ans * fac[n - circle_count] % mod;
        printf("%lld\n", ans);
    }
    return 0;
}