#include <stdio.h>
int main(void) {
while(t--)
{
int n,i,j,k; long long c=1;
long long a[1000001],p[n],na[n];
for(i=1;i<=n;i++){
p[a[i]]=a[i];
}//for
//change the positions accordingly
for(i=1;i<=n;i++){
na[i]=p[i];
}//for
for(j=1;j<=n;j++)
{
if(na[j]==a[j]){continue;}
else {for(k=1;k<=n;k++){na[k]=p[na[k]];}c++;}
}//forj
printf("%lld\n",c
%1000000007);
}//while
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiAKaW50IG1haW4odm9pZCkgewoJaW50IHQ7c2NhbmYoIiVkIiwmdCk7Cgl3aGlsZSh0LS0pCgl7CgkJaW50IG4saSxqLGs7IGxvbmcgbG9uZyBjPTE7CgkJc2NhbmYoIiVkIiwmbik7CgkJbG9uZyBsb25nIGFbMTAwMDAwMV0scFtuXSxuYVtuXTsKCQlmb3IoaT0xO2k8PW47aSsrKXsKCQkJc2NhbmYoIiVsZCIsJmFbaV0pOwoJCQlwW2FbaV1dPWFbaV07CgkJfS8vZm9yCgkJLy9jaGFuZ2UgdGhlIHBvc2l0aW9ucyBhY2NvcmRpbmdseQoJCWZvcihpPTE7aTw9bjtpKyspewoJCQluYVtpXT1wW2ldOwoJCX0vL2ZvcgoJCQlmb3Ioaj0xO2o8PW47aisrKQoJCQl7CgkJCQkKCQkJCWlmKG5hW2pdPT1hW2pdKXtjb250aW51ZTt9CgkJCQllbHNlIHtmb3Ioaz0xO2s8PW47aysrKXtuYVtrXT1wW25hW2tdXTt9YysrO30KCQkJCSAKCQkJCQoJCQkJfS8vZm9yagoJCQkKCQlwcmludGYoIiVsbGRcbiIsYyUxMDAwMDAwMDA3KTsKCQkKCX0vL3doaWxlCglyZXR1cm4gMDsKfQ==