#include <bits/stdc++.h>
#define mp make_pair
#define fir first
#define sec second
#define mt make_tuple
#define int long long
#define fin(File) freopen(File".in","r",stdin)
#define fout(File) freopen(File".out","w",stdout)
using namespace std;
namespace FastIO {
	//char *p1, *p2, buf[1 << 14];
	//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, (1 << 14), stdin), p1 == p2) ? EOF : *p1++)

	template <typename T>
	inline void read(T& x) {
    	x = 0;
    	register int t = 1;
    	register char ch = getchar();
    	while (ch < '0' || ch > '9') {
        	if (ch == '-')
            	t = -1;
        	ch = getchar();
    	}
    	while (ch >= '0' && ch <= '9'){
        	x = (x << 1) + (x << 3) + (ch ^ 48);
        	ch = getchar();
    	}
    	x *= t;
	}

	template <typename T>
	void write(T x) {
    	if (x < 0) {
        	putchar('-');
        	x = -x;
    	}
    	if (x > 9) write(x / 10);
    	putchar(x % 10 ^ 48);
	}

	template <typename T>
	inline void writeln(T x, char sep = '\n') {
		write(x);
		putchar(sep);
	}
}
const int N=1e6+10;
const int mod=1e9+7;
const int B=1010;
int isp[N],pre[N],inv[N];
vector <int> prime;
int qpow(int a,int b){
	a%=mod;int res=1;
	while(b){
		if(b&1)res=(res*a)%mod;
		b>>=1;a=(a*a)%mod;
	}return res;
}
void init(int n){
	for(int i=2;i<=n;i++){
		inv[i]=qpow(i,mod-2);
		if(!isp[i]){
			prime.push_back(i);
			pre[i]=i;
		}
		for(auto j:prime){
			if(i*j>n)break;
			isp[i*j]=1;pre[i*j]=j;
			if(i%j==0)break;
		}
	}
}
int T,n,p[N],vis[N],sz;
void C(int x){
	if(vis[x])return;
	vis[x]=1;sz++;C(p[x]);
}
map <int,map<int,int>> pw;
int Max(int x){
	map <int,int> &G=pw[x];
	if(!G.size())return 0;
	auto it=G.end();it--;
	while(G.size()&&it->sec==0){
		G.erase(it);
		if(!G.size())return 0;
		it=G.end();it--;
	}
	if(G.size()){
		return G.rbegin()->fir;
	}else return 0;
}
using namespace FastIO;
void solve(){
	read(n);pw.clear();
	for(int i=1;i<=n;i++)
		read(p[i]),vis[i]=0;
	map <int,int> m;
	int sum=0;
	for(int i=1;i<=n;i++){
		if(vis[i])continue;
		sz=0;C(i);m[sz]++;sum+=sz;
	}
	vector <int> a,b;
	for(auto it:m){
		a.push_back(it.fir);
		b.push_back(it.sec);
	}
	sz=a.size();
	for(int i=0;i<sz;i++){
		for(int j=1;j<=b[i];j++){
			int tmp=a[i];
			map <int,int> now;
			while(tmp!=1){
				now[pre[tmp]]++;
				tmp/=pre[tmp];
			}
			for(auto it:now){
				pw[it.fir][it.sec]++;
			}
		}
	}
	int res=0,lcm=1;
	for(auto it:pw){
		for(int i=1;i<=Max(it.fir);i++)
			lcm*=it.fir,lcm%=mod;
	}
	for(int i=0;i<sz;i++){
		for(int j=0;j<sz;j++){
			int sum=a[i]+a[j],X=0;
			if(i==j){
				X=(b[i]*a[i]%mod)*((b[i]-1+mod)*a[i]%mod)%mod;
			}else{
				X=(b[i]*a[i]%mod)*(b[j]*a[j]%mod)%mod;
			}
			map <int,int> now;
			int tmp=sum;
			while(tmp!=1){
				now[pre[tmp]]++;
				tmp/=pre[tmp];
			}
			vector <tuple<int,int,int>> undo;
			undo.reserve(50);
			for(auto it:now){
				undo.push_back(mt(it.fir,it.sec,-1));
				int lst=Max(it.fir);
				pw[it.fir][it.sec]++;
				int nxt=Max(it.fir);
				if(nxt-lst>=0){
					lcm*=qpow(it.fir,nxt-lst);
				}else{
					lcm*=qpow(inv[it.fir],lst-nxt);
				}
				lcm%=mod;
			}
			tmp=a[i];now.clear();
			while(tmp!=1){
				now[pre[tmp]]++;
				tmp/=pre[tmp];
			}
			for(auto it:now){
				undo.push_back(mt(it.fir,it.sec,1));
				int lst=Max(it.fir);
				pw[it.fir][it.sec]--;
				int nxt=Max(it.fir);
				if(nxt-lst>=0){
					lcm*=qpow(it.fir,nxt-lst);
				}else{
					lcm*=qpow(inv[it.fir],lst-nxt);
				}
				lcm%=mod;
			}
			tmp=a[j];now.clear();
			while(tmp!=1){
				now[pre[tmp]]++;
				tmp/=pre[tmp];
			}
			for(auto it:now){
				undo.push_back(mt(it.fir,it.sec,1));
				int lst=Max(it.fir);
				pw[it.fir][it.sec]--;
				int nxt=Max(it.fir);
				if(nxt-lst>=0){
					lcm*=qpow(it.fir,nxt-lst);
				}else{
					lcm*=qpow(inv[it.fir],lst-nxt);
				}
				lcm%=mod;
			}
			res+=X*lcm%mod;res%=mod;
			reverse(undo.begin(),undo.end());
			for(auto it:undo){
				int x=get<0>(it),y=get<1>(it),z=get<2>(it);
				int lst=Max(x);
				pw[x][y]+=z;
				int nxt=Max(x);
				if(nxt-lst>=0){
					lcm*=qpow(x,nxt-lst);
				}else{
					lcm*=qpow(inv[x],lst-nxt);
				}
				lcm%=mod;
			}
		}
	}
	writeln(res);
}
signed main(){
	//ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//fin("perm");fout("perm");
	init(1e6);read(T);
	while(T--)solve();
	//cerr<<1.0*clock()/CLOCKS_PER_SEC<<endl;
	return 0;
}