#include<iostream>
using namespace std;
int gcd(int a,int b);
int main()
{
unsigned long arr1[10000]={0},arr2[10000]={0},arr3[10000]={0};
int cases,i,j,total,x,k,b=0;
cin>>cases;
for(k=0;k<cases;++k)
{
cin>>total;
for(i=1;i<=total;++i)
{
cin>>arr1[i];
arr3[i]=arr1[i];
}
for(i=1;i<=total;i++)
{
if(arr1[i]!=i)
break;
else
b++;
}
for(i=1,j=1;i<=total,j<=total;++i,++j)
{
while(arr1[i]!=i)
{
x=arr1[arr1[i]];
arr1[i]=x;
arr2[j]++;
}
arr1[i]=arr3[i];
}
for(i=1;i<=total;++i)
{
arr2[i]=(1+arr2[i]);
}
int lcm;
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)
cout<<1<<endl;
else
cout<<(lcm%(1000000000+7))<<endl;
lcm=0;
x=0,i=0,j=0,b=0;
for(i=1;i<=total;++i)
{
arr1[i]=0;
arr2[i]=0;
arr3[i]=0;
}
}
return 0;
}
int gcd(int a,int b)
{
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+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CmludCBnY2QoaW50IGEsaW50IGIpOwppbnQgbWFpbigpCnsKICAgIHVuc2lnbmVkIGxvbmcgYXJyMVsxMDAwMF09ezB9LGFycjJbMTAwMDBdPXswfSxhcnIzWzEwMDAwXT17MH07CiAgICBpbnQgY2FzZXMsaSxqLHRvdGFsLHgsayxiPTA7CiAgICBjaW4+PmNhc2VzOwogICAgZm9yKGs9MDtrPGNhc2VzOysraykKICAgIHsKICAgIGNpbj4+dG90YWw7CiAgICBmb3IoaT0xO2k8PXRvdGFsOysraSkKICAgIHsKICAgICAgIGNpbj4+YXJyMVtpXTsKICAgICAgIGFycjNbaV09YXJyMVtpXTsKICAgIH0KICAgIGZvcihpPTE7aTw9dG90YWw7aSsrKQogICAgewogICAgICAgIGlmKGFycjFbaV0hPWkpCiAgICAgICAgICAgIGJyZWFrOwogICAgICAgIGVsc2UKICAgICAgICAgICAgYisrOwogICAgfQoKICAgIGZvcihpPTEsaj0xO2k8PXRvdGFsLGo8PXRvdGFsOysraSwrK2opCiAgICB7CiAgICB3aGlsZShhcnIxW2ldIT1pKQogICAgewogICAgeD1hcnIxW2FycjFbaV1dOwogICAgYXJyMVtpXT14OwogICAgYXJyMltqXSsrOwogICAgfQoKICAgIGFycjFbaV09YXJyM1tpXTsKICAgIH0KICAgIGZvcihpPTE7aTw9dG90YWw7KytpKQogICAgewogICAgICAgIGFycjJbaV09KDErYXJyMltpXSk7CiAgICB9CgoKaW50IGxjbTsKbGNtPWFycjJbMV0qYXJyMlsyXS9nY2QoYXJyMlsxXSxhcnIyWzJdKTsKZm9yKGk9MztpPD10b3RhbDtpKyspCiAgICAgICAgICAgICAgICAgIGxjbT1sY20qYXJyMltpXS9nY2QobGNtLGFycjJbaV0pOwoKaWYoYj09dG90YWwpCmNvdXQ8PDE8PGVuZGw7CmVsc2UKY291dDw8KGxjbSUoMTAwMDAwMDAwMCs3KSk8PGVuZGw7CmxjbT0wOwp4PTAsaT0wLGo9MCxiPTA7CmZvcihpPTE7aTw9dG90YWw7KytpKQp7CiAgICBhcnIxW2ldPTA7CiAgICBhcnIyW2ldPTA7CiAgICBhcnIzW2ldPTA7Cn0KICAgIH0KcmV0dXJuIDA7Cn0KCmludCBnY2QoaW50IGEsaW50IGIpCnsKICAgIGludCByZW07CiAgICBpZihiPT0wKQogICAgcmV0dXJuIGE7CiAgICBpZihhPT0wKQogICAgcmV0dXJuIGI7CiAgICBpZihiPmEpCiAgICB7CiAgICAgICAgICAgYT1hK2I7CiAgICAgICAgICAgYj1hLWI7CiAgICAgICAgICAgYT1hLWI7CiAgICAgICAgICAgfQogICAgICAgICAgIHJlbT1hJWI7CiAgICB3aGlsZShyZW0+YikKICAgIHsKICAgICAgICAgICAgICBhPWI7CiAgICAgICAgICAgICAgYj1yZW07CiAgICAgICAgICAgICAgcmVtPWElYjsKICAgIH0KICAgICAgICAgICAgICBpZihyZW09PTApCiAgICAgICAgICAgICAgcmV0dXJuIGI7CiAgICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgIHJldHVybiByZW07Cn0KCgo=