#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=3030,mod=998244353;
int n,m,a[N],cnt[N],vis[N],pd[N];
LL ans,f[N],fac[N],inv[N];
LL ksm(LL x,int y)
{
	LL ret=1;
	while(y)
	{
		if(y&1)
		{
			ret=ret*x%mod; 
		}
		x=x*x%mod;
		y>>=1;
	}
	return ret;
}
int gcd(int x,int y)
{
	if(y==0)
	{
		return x;
	}
	return gcd(y,x%y);
}
void work()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		cnt[i]=0;vis[i]=0;
	}
	fac[0]=1;
	for(int i=1;i<=n;i++)
	{
		fac[i]=fac[i-1]*i%mod;
	}
	inv[n]=ksm(fac[n],mod-2);
	for(int i=n-1;i>=0;i--)
	{
		inv[i]=inv[i+1]*(i+1)%mod;
	//	cout<<inv[i]<<endl;
	}
	for(int i=1;i<=n;i++)
	{
		if(vis[i]==0)
		{
			int len=1;
			vis[i]=1;
			for(int j=a[i];j!=i;j=a[j])
			{
				vis[j]=1;
				len++;
			}
			cnt[len]++;
		}
	}
//	cout<<"ye\n";
	LL ans=1;
	for(int i=1;i<=n;i++)
	{
		//knapsack of l1,l2,..,lm,(l1+..+lm)=cnt[i],fac[l1-1]*i^(l1-1)
		f[0]=1;
		for(int j=1;j<=cnt[i];j++)
		{
			int len=j*i;
			if(len/gcd(len,m)==i)
			{
				pd[j]=1;
			}else{
				pd[j]=0;
			}
		}
		for(int k=1;k<=cnt[i];k++)
		{
			f[k]=0;
			for(int j=1;j<=k;j++)
			{
				if(pd[j]==0)
				{
					continue; 
				}
				int len=j*i;
				if(len/gcd(len,m)!=i)
				{
					continue;
				}
				f[k]+=f[k-j]*fac[k-1]%mod*inv[j-1]%mod*inv[k-j]%mod
				*ksm(i,j-1)%mod*fac[j-1]%mod;
				f[k]%=mod;
			}
		//	cout<<k<<' '<<f[k]<<endl;
		}
		ans*=f[cnt[i]];
		ans%=mod;
	}
	printf("%lld\n",ans);
}
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		work();
	}
	return 0;
}