#include<iostream>
using namespace std;
int gcd(int a,int b); //to find GCD of 2 nos
int main()
{
unsigned long arr1[10000]={0},arr2[10000]={0},arr3[10000]={0};
int cases,i,j,total,x,k,b=0;
cin>>cases; //total no of test cases
for(k=0;k<cases;++k)
{
cin>>total; // total no. of bandits
for(i=1;i<=total;++i)
{
cin>>arr1[i]; //each unique location stored in arr1 & arr2
arr3[i]=arr1[i];
}
for(i=1;i<=total;i++) //if all are in right places, they stop after Ist whistle
{
if(arr1[i]!=i)
break;
else
b++;
}
for(i=1,j=1;i<=total,j<=total;++i,++j)
{
while(arr1[i]!=i) //while they're in incorrect positions
{
x=arr1[arr1[i]];
arr1[i]=x; //arr1[i] gets updated to arr1[arr1[i]]; Verify this by taking a case
arr2[j]++; //I wish to calculate LCM of the values this arr2 stores
}
arr1[i]=arr3[i]; //this resets value of arr1
}
for(i=1;i<=total;++i)
{
arr2[i]=(1+arr2[i]);//increases the value of each element by 1(as I couldn't initialize entire array with one) )
}
unsigned long long lcm; //simple fn to calc. lcm using GCD
lcm=arr2[1]*arr2[2]/gcd(arr2[1],arr2[2]);
for(i=3;i<=total;i++)
lcm=lcm*arr2[i]/gcd(lcm,arr2[i]);
if(b==total) //if all in right place output 1
cout<<1<<endl;
else
cout<<(lcm%(1000000000+7))<<endl; //o/w output modulo of the lcm
lcm=0;
x=0,i=0,j=0,b=0;
for(i=1;i<=total;++i) //initialzing all the arrays
{
arr1[i]=0;
arr2[i]=0;
arr3[i]=0;
}
}
return 0;
}
int gcd(int a,int b) //GCD fn
{
int rem;
if(b==0)
return a;
if(a==0)
return b;
if(b>a)
{
a=a+b;
b=a-b;
a=a-b;
}
rem=a%b;
while(rem>b)
{
a=b;
b=rem;
rem=a%b;
}
if(rem==0)
return b;
else
return rem;
}
I2luY2x1ZGU8aW9zdHJlYW0+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CmludCBnY2QoaW50IGEsaW50IGIpOyAgICAvL3RvIGZpbmQgR0NEIG9mIDIgbm9zCmludCBtYWluKCkKewogICAgdW5zaWduZWQgbG9uZyBhcnIxWzEwMDAwXT17MH0sYXJyMlsxMDAwMF09ezB9LGFycjNbMTAwMDBdPXswfTsKICAgIGludCBjYXNlcyxpLGosdG90YWwseCxrLGI9MDsKICAgIGNpbj4+Y2FzZXM7ICAgICAgICAgICAvL3RvdGFsIG5vIG9mIHRlc3QgY2FzZXMKICAgIGZvcihrPTA7azxjYXNlczsrK2spCiAgICB7CiAgICBjaW4+PnRvdGFsOyAgICAgICAgICAgLy8gdG90YWwgbm8uIG9mIGJhbmRpdHMKICAgIGZvcihpPTE7aTw9dG90YWw7KytpKQogICAgewogICAgICAgY2luPj5hcnIxW2ldOyAgICAgICAvL2VhY2ggdW5pcXVlIGxvY2F0aW9uIHN0b3JlZCBpbiBhcnIxICYgYXJyMgogICAgICAgYXJyM1tpXT1hcnIxW2ldOwogICAgfQogICAgZm9yKGk9MTtpPD10b3RhbDtpKyspICAvL2lmIGFsbCBhcmUgaW4gcmlnaHQgcGxhY2VzLCB0aGV5IHN0b3AgYWZ0ZXIgSXN0IHdoaXN0bGUKICAgIHsKICAgICAgICBpZihhcnIxW2ldIT1pKQogICAgICAgICAgICBicmVhazsKICAgICAgICBlbHNlCiAgICAgICAgICAgIGIrKzsKICAgIH0KCiAgICBmb3IoaT0xLGo9MTtpPD10b3RhbCxqPD10b3RhbDsrK2ksKytqKQogICAgewogICAgd2hpbGUoYXJyMVtpXSE9aSkgICAgIC8vd2hpbGUgdGhleSdyZSBpbiBpbmNvcnJlY3QgcG9zaXRpb25zCiAgICB7CiAgICB4PWFycjFbYXJyMVtpXV07ICAgICAgCiAgICBhcnIxW2ldPXg7ICAgICAgICAgICAgLy9hcnIxW2ldIGdldHMgdXBkYXRlZCB0byBhcnIxW2FycjFbaV1dOyBWZXJpZnkgdGhpcyBieSB0YWtpbmcgYSBjYXNlCiAgICBhcnIyW2pdKys7ICAgICAgICAgICAgLy9JIHdpc2ggdG8gY2FsY3VsYXRlIExDTSBvZiB0aGUgdmFsdWVzIHRoaXMgYXJyMiBzdG9yZXMKICAgIH0KCiAgICBhcnIxW2ldPWFycjNbaV07ICAgICAgLy90aGlzIHJlc2V0cyB2YWx1ZSBvZiBhcnIxCiAgICB9CiAgICBmb3IoaT0xO2k8PXRvdGFsOysraSkKICAgIHsKICAgICAgICBhcnIyW2ldPSgxK2FycjJbaV0pOy8vaW5jcmVhc2VzIHRoZSB2YWx1ZSBvZiBlYWNoIGVsZW1lbnQgYnkgMShhcyBJIGNvdWxkbid0IGluaXRpYWxpemUgZW50aXJlIGFycmF5IHdpdGggb25lKSApCiAgICB9CgoKdW5zaWduZWQgbG9uZyBsb25nIGxjbTsgICAgICAgICAgICAvL3NpbXBsZSBmbiB0byBjYWxjLiBsY20gdXNpbmcgR0NECmxjbT1hcnIyWzFdKmFycjJbMl0vZ2NkKGFycjJbMV0sYXJyMlsyXSk7CmZvcihpPTM7aTw9dG90YWw7aSsrKQogICAgICAgICAgICAgICAgICBsY209bGNtKmFycjJbaV0vZ2NkKGxjbSxhcnIyW2ldKTsKCmlmKGI9PXRvdGFsKSAgICAgICAgICAgICAgICAgICAgICAgLy9pZiBhbGwgaW4gcmlnaHQgcGxhY2Ugb3V0cHV0IDEKY291dDw8MTw8ZW5kbDsKZWxzZQpjb3V0PDwobGNtJSgxMDAwMDAwMDAwKzcpKTw8ZW5kbDsgLy9vL3cgb3V0cHV0IG1vZHVsbyBvZiB0aGUgbGNtCmxjbT0wOwp4PTAsaT0wLGo9MCxiPTA7CmZvcihpPTE7aTw9dG90YWw7KytpKSAvL2luaXRpYWx6aW5nIGFsbCB0aGUgYXJyYXlzIAp7CiAgICBhcnIxW2ldPTA7CiAgICBhcnIyW2ldPTA7CiAgICBhcnIzW2ldPTA7Cn0KICAgIH0KcmV0dXJuIDA7Cn0KCmludCBnY2QoaW50IGEsaW50IGIpICAvL0dDRCBmbgp7CiAgICBpbnQgcmVtOwogICAgaWYoYj09MCkKICAgIHJldHVybiBhOwogICAgaWYoYT09MCkKICAgIHJldHVybiBiOwogICAgaWYoYj5hKQogICAgewogICAgICAgICAgIGE9YStiOwogICAgICAgICAgIGI9YS1iOwogICAgICAgICAgIGE9YS1iOwogICAgICAgICAgIH0KICAgICAgICAgICByZW09YSViOwogICAgd2hpbGUocmVtPmIpCiAgICB7CiAgICAgICAgICAgICAgYT1iOwogICAgICAgICAgICAgIGI9cmVtOwogICAgICAgICAgICAgIHJlbT1hJWI7CiAgICB9CiAgICAgICAgICAgICAgaWYocmVtPT0wKQogICAgICAgICAgICAgIHJldHVybiBiOwogICAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgICByZXR1cm4gcmVtOwp9CgoK