#include <bits/stdc++.h> //by: hansang
using namespace std;
typedef long long LL;
const int N=1e5+10;
const LL P=1e9+9;
LL p[N], fac[N], f[N], L[N]; int cnt; bool v[N];
LL q_pow(LL a, LL b)
{
	LL res=1%P; a%=P;
	for(; b; b>>=1)
	{
		if(b&1) res=res*a%P;
		a=a*a%P;
	}
	return res;
}
LL dfs(int x)
{
	v[x]=1;
	if(v[p[x]]==1) return 1;
	else return dfs(p[x])+1;
}
int main()
{
	fac[0]=1; for(int i=1; i<=N-10; i++) fac[i]=fac[i-1]*i%P;
	f[1]=1; for(int i=2; i<=N-10; i++) f[i]=q_pow(i, i-2);
	int T; scanf("%d", &T);
	while(T--)
	{
		int n; LL ans; scanf("%d", &n);
		for(int i=1; i<=n; i++) scanf("%lld", &p[i]);
		memset(v, 0, sizeof(v)); cnt=0;
		for(int i=1; i<=n; i++) if(v[i]==0) L[++cnt]=dfs(i);
		ans=fac[n-cnt]%P;
		for(int i=1; i<=cnt; i++) 
		{
			LL inv=q_pow(fac[L[i]-1], P-2);
			ans=(ans*f[L[i]]%P*inv%P)%P;
		}
		printf("%lld\n", ans);
	}
	return 0;
}

#include<bits/stdc++.h> //by: hansang
using namespace std;
typedef long long LL;
const int N=1e5+10;
const LL P=1e9+9;
LL p[N], fac[N], f[N], L[N]; int cnt; bool v[N];
LL q_pow(LL a, LL b)
{
	LL res=1%P; a%=P;
	for(; b; b>>=1)
	{
		if(b&1) res=res*a%P;
		a=a*a%P;
	}
	return res;
}
LL dfs(int x)
{
	v[x]=1;
	if(v[p[x]]==1) return 1;
	else return dfs(p[x])+1;
}
int main()
{
	fac[0]=1; for(int i=1; i<=N-10; i++) fac[i]=fac[i-1]*i%P;
	f[1]=1; for(int i=2; i<=N-10; i++) f[i]=q_pow(i, i-2);
	int T; scanf("%d", &T);
	while(T--)
	{
		int n; LL ans; scanf("%d", &n);
		for(int i=1; i<=n; i++) scanf("%lld", &p[i]);
		memset(v, 0, sizeof(v)); cnt=0;
		for(int i=1; i<=n; i++) if(v[i]==0) L[++cnt]=dfs(i);
		ans=fac[n-cnt]%P;
		for(int i=1; i<=cnt; i++) 
		{
			LL inv=q_pow(fac[L[i]-1], P-2);
			ans=(ans*f[L[i]]%P*inv%P)%P;
		}
		printf("%lld\n", ans);
	}
	return 0;
}