#include<stdio.h>
 #include<cstring>
 #include<cmath>
 #include<algorithm>
 #include<set>
 using namespace std;
 *1e6+;
 ;
 int n, T;
 int a[MAXN];
 int vis[MAXN];
 int num[MAXN];
 int tmp;
 int t;
 int ct;
 long long ans;
 set<int>s;
 set<int>::iterator it;
 int cnt[MAXN];
 int main(){
     scanf("%d",&T);
     while(T--){
         t = ;
         scanf("%d",&n);
         ; i <= n; ++i){
             scanf("%d",&a[i]);
         }
         memset(vis,,sizeof(vis));
         ; i <= n; ++i){
              )
                 continue;
             tmp = a[a[i]];
             num[t] = ;
             while( a[i] != tmp ){
                 vis[tmp] = ;
                 tmp = a[tmp];
                 num[t]++;
             }
             vis[tmp] = ;
             t++;
         }
         memset(cnt,,sizeof(cnt));
         ans = ;
         ; i < t; ++i){
             ; d <= num[i]; ++d){
                 ct = ;
                  ){
                     num[i] = num[i] / d;
                     ct++;
                 }
                 s.insert(d);
                 cnt[d] = max(cnt[d],ct);
             }
         }
         for(it = s.begin();it!=s.end();++it){
             ans = ans*pow((*it),cnt[*it]);
             ans %= MOD;
         }
         printf("%I64d\n",ans);
     }
 }