#include <bits/stdc++.h>
#define N 3010
#define int long long

using namespace std;

const int mod = 998244353;

int t, n, m, k, a[N], dp[N], vis[N], cnt[N];
vector <int> arr;

namespace Math {
    
    const int M = 3000;

    int fac[N], ifac[N];

    inline void add(int &x, int y) {
        x = (x + y) % mod;
    }

    inline int power(int a, int b) {
        int res = 1;
        while(b) {
            if(b & 1)
                res = res * a % mod;
            a = a * a % mod;
            b >>= 1;
        }
        return res;
    }

    inline void pre() {
        
        fac[0] = ifac[0] = 1;
        for(int i = 1; i <= M; i++)
            fac[i] = fac[i - 1] * i % mod;

        ifac[M] = power(fac[M], mod - 2);
        for(int i = M - 1; i; i--)
            ifac[i] = ifac[i + 1] * (i + 1) % mod;
    
    }

    inline int C(int n, int m) {
        if(n < 0 || m < 0 || n - m < 0)
            return 0;
        return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
    }
}

using namespace Math;

inline int solve(int n, int m) {

    arr.clear();
    memset(dp, 0, sizeof dp);

    for(int i = 1; i <= n; i++)
        if(__gcd(m * i, k) == i)
            arr.push_back(i);

    dp[0] = 1;
    for(int i = 1; i <= n; i++){
        for(int u : arr) {
            if(u > i)
                break;
            dp[i] = dp[i - u] * C(i - 1, u - 1) % mod * fac[u - 1] % mod * power(m, u - 1) % mod;
        }
    }   

    return dp[n];
}

signed main() {

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    pre();

    cin >> t;
    
    while(t--) {
        
        memset(vis, 0, sizeof vis);
        memset(cnt, 0, sizeof cnt);

        cin >> n >> k;

        for(int i = 1; i <= n; i++)
            cin >> a[i];
        
        for(int i = 1; i <= n; i++) {
            if(vis[i])
                continue;
            int u = i, sz = 0;

            while(!vis[u]){
                vis[u] = 1;
                ++sz;
                u = a[u];
            }
        
            cnt[sz]++;
        }

        int ans = 1;

        for(int i = 1; i <= n; i++)
            if(cnt[i])
                ans = ans * solve(cnt[i], i) % mod;

        cout << ans << endl;
    }
}