#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
#define mst(a,x) memset(a,x,sizeof(a))
using namespace std;

const int N = 3000005;
const ll MOD = 3221225473;
int c[N], a[N], g, tot, n, num[N];
bool vis[N];

int gcd(int x, int y)
{
    return  !y ? x : gcd(y, x % y);
}

int read()
{
    char ch;
    int ret = 0;
    while(ch = getchar(), ch < '0' || ch > '9');
    ret = ch ^ 48;
    while(ch = getchar(), ch >= '0' && ch <= '9') {
        ret = ret * 10  + (ch ^ 48);
    }
    return ret;
}

int main()
{
    int T;

    scanf("%d", &T);
    while(T--)
    {
        n = read();
        for(int i = 1; i <= n; i++)
        {
            a[i] = read();
            vis[i] = 0;
            num[i] = 0;
        }
        tot = 0;
        for(int i = 1; i <= n; i++)
        {
            if(vis[i]) continue;
            c[tot] = 0;
            for(int y = i; !vis[y]; y = a[y])
            {
                vis[y] = 1;
                c[tot]++;
            }
            tot++;
        }
        for(int i = 0; i < tot; i++) 
        {
            int x = c[i];
            for(int j = 2; j <= x; j++)
            {
                if(x % j == 0)
                {
                    int cnt = 0;
                    while(x % j == 0)
                    {
                        x /= j;
                        cnt++;
                    }
                    num[j] = max(num[j], cnt);
                }
            }
        }
        ll ans = 1;
        for(int i = 2; i <= n; i++)
        {
            if(num[i]) 
            {
                for(int j = 0; j < num[i]; j++)
                    ans = ans * i % MOD;
            }
        }
        printf("%I64d\n", ans);
    }
    return 0;
}