#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n;
int T;
int a[3000006];
bool vis[3000006];
int prime[3000006];
bool isprime[3000006];
int g[3000006];
const long long MOD=3221225473;
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*10+ch-'0';ch=getchar();}
    return x*f;
}
int cnt=0;
void get()
{
    for(int i=2;i<=3000000;i++)
    {
        if(!isprime[i])
        {
            cnt++;
            prime[cnt]=i;
        }
        for(int j=1;j<=cnt;j++)
        {
            if(prime[j]*i>3000000)break;
            isprime[prime[j]*i]=true;
            if(i%prime[j]==0)break;
        }
    }
}
void add(int x)
{
    for(int i=1;i<=cnt;i++)
    {
        if(x==1)break;
        if(x%prime[i])continue;
        int pp=0;
        while(x%prime[i]==0)
        {
            pp++;
            x/=prime[i];
        }
        g[i]=max(g[i],pp);
    }
}
int main()
{
    T=read();
    get();
    while(T--)
    {
        n=read();
        for(int i=1;i<=n;i++)
        {
            g[i]=0;
            a[i]=read();
        }
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=n;i++)
        {
            if(vis[i])continue;
            int pp=1;
            int now=a[i];
            vis[i]=true;
            while(now!=i)
            {
                pp++;
                vis[now]=true;
                now=a[now];
            }
            add(pp);
        }
        long long ans=1;
        for(int i=1;i<=cnt;i++)
        {
            for(int j=1;j<=g[i];j++)
            {
                ans=ans*(long long)prime[i]%MOD;
            }
        }
        printf("%I64d\n",ans);
    }
    return 0;
}