#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#define N 3000005
using namespace std;
const long long Mo=3*(1ll<<30ll)+1;
int i,j,m,n,p[N],k,a[N],vis[N],prime[N],tot,Min[N],Q[N],R[N],sum[N];
int read()
{
      int x=0; char c;
      while (c=getchar(),c<'0'||c>'9'); x=c-'0';
      while (c=getchar(),c>='0'&&c<='9') x=(x<<1)+(x<<3)+c-'0';
      return x;
}
long long power(int x,int y)
{
      long long sum=1;
      for (;y;y>>=1)
      {
           if (y&1) sum=1ll*sum*x%Mo;
           x=1ll*x*x%Mo;
      }
      return sum;
}
void pre()
{
      for (i=2;i<N;++i)
      {
          if (!vis[i]) prime[++tot]=i,Min[i]=i;
          for (j=1;j<=tot&&prime[j]*i<N;++j)
          {
               vis[i*prime[j]]=1;
               Min[i*prime[j]]=min(Min[i],prime[j]);
               if (i%prime[j]==0) break;
         }
     }
}
int main()
{
      int T;
      scanf("%d",&T);
      pre();
      memset(vis,0,sizeof(vis));
      for (k=1;k<=T;++k)
{
       scanf("%d",&n); memset(p,0,sizeof(p)); 
       for (i=1;i<=n;++i) a[i]=read();
       Q[0]=0;
       for (i=1;i<=n;++i)
          if (vis[i]!=k)
          { 
               int Sum=0;
                for (j=i;vis[j]!=k;j=a[j]) vis[j]=k,++Sum;
                Q[++Q[0]]=Sum;
          }
       for (i=1;i<=Q[0];++i)
       {
             R[0]=0;
             while (Q[i]>1)
             { 
                 if (!R[0]||R[R[0]]!=Min[Q[i]]) R[++R[0]]=Min[Q[i]],sum[R[0]]=1;
                 else sum[R[0]]++;
                 Q[i]/=Min[Q[i]];
             }
             for (j=1;j<=R[0];++j) p[R[j]]=max(p[R[j]],sum[j]);
       }
       long long ans=1;
       for (i=2;i<=n;++i) if (p[i]) ans=1ll*ans*power(i,p[i])%Mo;
       cout<<ans<<endl;
}
}