#include<bits/stdc++.h>
#define int long long
using namespace std;
void ts(){cout<<"IAKIOI\n";}
inline int read(){
	int n=0,f=1,ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		n=n*10+ch-'0';
		ch=getchar();
	}
	return n*f;
}
int n;
int a[605];
int f[605];
const int mod=1e9+7;
bool chk(int x){
	int l=1,r=(int)1e9;
	int res=-1;
	while(l<=r){
		int mid=(l+r)/2;
		if(mid*mid<=x){
			res=mid,l=mid+1;
		}
		else r=mid-1;
	}
	return res*res==x;
}
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
int l;
int b[605];
int dp[605][605];
int fac[605];
int C[2005][2005];
//前 i 组考虑下来, 有 j 个相邻的相同的.
void solve(){
	n=read();
	for(int i=1;i<=n;i++)a[i]=read(),f[i]=i;
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			int m=a[i]*a[j];
			if(chk(m)){
				f[find(i)]=find(j);
			}
		}
	}
	l=0;
	vector<int> cnt(n+1,0);
	for(int i=1;i<=n;i++)cnt[find(i)]++;
	for(int i=1;i<=n;i++){
		if(cnt[i])b[++l]=cnt[i];
	}
	sort(b+1,b+l+1);
	int coef=1;
	for(int i=1;i<=l;i++)coef*=fac[b[i]],coef%=mod;
	//for(int i=1;i<=l;i++)cout<<b[i]<<" ";
	//cout<<"\n";
	memset(dp,0,sizeof(dp));
	dp[1][b[1]-1]=1;
	int pre=b[1];
	for(int i=2;i<=l;i++){
		for(int j=0;j<=n;j++){
			if(!dp[i-1][j])continue;
			//j 个相邻的是相同的.
			//去掉旧的 x 个相同的.
			//分成 k 组.
			for(int k=1;k<=min(b[i],pre+1);k++){
				for(int x=0;x<=min(j,k);x++){
					//考虑分成
					dp[i][j-x+b[i]-k]+=C[b[i]-1][k-1]*C[j][x]%mod*C[pre+1-j][k-x]%mod*dp[i-1][j]%mod;
					dp[i][j-x+b[i]-k]%=mod;
				}
			}
		}
		pre+=b[i];
	}
	cout<<dp[l][0]*coef%mod<<"\n";
}
signed main(){
	fac[0]=1;
	for(int i=1;i<605;i++)fac[i]=fac[i-1]*i%mod;
	C[0][0]=1;
	for(int i=1;i<=2000;i++){
		C[i][0]=C[i][i]=1;
		for(int j=1;j<i;j++)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
	}
	int t=read();
	while(t--)solve();
	return 0;
}
//look at my code
//my code is amazing