#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
const int N=5000,mod=998244353;
typedef long long ll;
ll Fact[N+5],inv[N+5];
ll inverse(int x){
    return inv[x]*Fact[x-1]%mod;
}
void pre(){
    Fact[0]=Fact[1]=inv[0]=inv[1]=1;
    for(int i=2;i<=N;i++){
        Fact[i]=i*Fact[i-1]%mod;
        inv[i]=mod-mod/i*inverse(mod%i)%mod;
        inv[i]=inv[i]*inv[i-1]%mod;
    }
}
ll Power(ll x,ll n){
    ll res=1;
    while(n){
        if(n&1)res=res*x%mod;
        x=x*x%mod;
        n>>=1;
    }
    return res;
}
ll C(ll n,ll r){
    return Fact[n]*inv[n-r]%mod*inv[r]%mod;
}
ll Calc(ll n,ll k,ll len){//merge k cycles with length len from n cycles;
    return C(n-1,k-1)*Fact[k-1]%mod*Power(len,k-1)%mod;
}
ll Solve(ll n,ll m,ll K){//n cycles of length m
    ll dp[n+1]={};
    dp[0]=1;
    vector<int>v;
    for(int i=1;i<=n;i++){
        if(__gcd(m*i,K)==i)v.push_back(i);
    }
    for(int i=1;i<=n;i++){
        for(auto&j:v){
            if(j>i)break;
            dp[i]+=dp[i-j]*Calc(i,j,m)%mod;
        }
        dp[i]%=mod;
    }
    return dp[n];
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    pre();
    int t;
    cin>>t;
    while(t--){
        int n,K;
        cin>>n>>K;
        int a[n],vis[n]={},freq[n+1]={};
        for(int i=0;i<n;i++)cin>>a[i],a[i]--;
        for(int i=0;i<n;i++){
            if(vis[i])continue;
            int x=i,sz=0;
            while(!vis[x]){
                sz++;
                vis[x]=1;
                x=a[x];
            }
            freq[sz]++;
        }
        ll res=1;
        for(int i=1;i<=n;i++){
            if(freq[i])res=res*Solve(freq[i],i,K)%mod;
        }
        cout<<res<<"\n";
    }
    return 0;
}