#include <bits/stdc++.h>
#define N 12010
#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;

namespace Polynomial {
    typedef vector <int> poly;
    int rev[N];
    const int G = 3, invG = power(G, mod - 2), inv2 = power(2, mod - 2);

    inline void reset(poly A) {
        for(int i = 0; i < A.size(); i++)
            A[i] = 0;
    }

    poly Mul_Con(poly A, int C) {
        for(int i = 0; i < A.size(); i++)
            A[i] *= C;
        return A;
    }

    inline int initrev(const int n) {
        int len = 1;
        while(len <= n)
            len <<= 1;
        for(int i = 0; i < len; i++) {
            rev[i] = rev[i >> 1] >> 1;
            if(i & 1)
                rev[i] |= len >> 1;
        }
        return len;
    }

    inline poly Diff(poly arr) {
        const int n = arr.size();
        for(int i = 1; i < n; i++) 
            arr[i - 1] = arr[i] * i % mod;
        arr.resize(n - 1);
        return arr;
    }
    
    inline poly Inte(poly arr) {
        const int n = arr.size();
        arr.resize(n + 1);
        for(int i = n; i; i--) {
            arr[i] = arr[i - 1] * power(i, mod - 2) % mod;
        }
        arr[0] = 0;
        return arr;
    }
    
    inline void NTT(poly &arr, const int len, const int op) {
        arr.resize(len);
        for(int i = 0; i < len; i++) {
            if(i < rev[i])
                swap(arr[i], arr[rev[i]]);
        }
        for(int i = 2; i <= len; i <<= 1) {
            int wn = power(op ? G : invG, (mod - 1) / i);
            for(int j = 0; j < len; j += i) {
                int w = 1;
                for(int k = j; k < j + i / 2; k++, w = 1ll * w * wn % mod) {
                    int x = arr[k], y = 1ll * w * arr[k + i / 2] % mod;
                    arr[k] = (x + y) % mod;
                    arr[k + i / 2] = (x - y + mod) % mod;
                } 
            }
        }
        if(op)
            return;
        int invn = power(len, mod - 2);
        for(int i = 0; i < len; i++)
            arr[i] = arr[i] * invn % mod;
    }

    inline poly Mul(poly A, poly B) {

        int n = A.size() + B.size() - 1, len = initrev(n);
        poly C;
        C.resize(len);
        NTT(A, len, 1);
        NTT(B, len, 1);
        for(int i = 0; i < len; i++) {
            C[i] = A[i] * B[i] % mod;
        }
        NTT(C, len, 0);
        C.resize(n);
        return C;
    }

    inline poly Inv(poly arr, const int n) {
        if(n == 1) {
            return poly(1, power(arr[0], mod - 2));
        }
        poly A(arr.begin(), arr.begin() + n);
        poly B = Inv(arr, (n + 1) >> 1);
        int len = initrev(n << 1);
        NTT(A, len, 1);
        NTT(B, len, 1);

        for(int i = 0; i < len; i++) {

            A[i] = 1ll * B[i] * (2 - 1ll * A[i] * B[i] % mod + mod) % mod;
        }
        NTT(A, len, 0);
        A.resize(n);
        return A;   
    }

    //!  arr[0] = 1;
    poly Sqrt(poly arr, int n) {
        if(n == 1)
            return poly(1, 1);
        poly A(arr.begin(), arr.begin() + n);
        poly B = Sqrt(arr, (n + 1) >> 1);
        B.resize(n);
        poly C = Inv(B, n);
        const int len = initrev(n << 1);
        NTT(A, len, 1);
        NTT(C, len, 1);
        for(int i = 0; i < len; i++) 
            A[i] = A[i] * C[i] % mod;
        NTT(A, len, 0);
        for(int i = 0; i < n; i++) 
            A[i] = (A[i] + B[i]) * inv2 % mod;
        A.resize(n);
        return A;
    }

    inline poly Ln(poly arr, int n) {
        poly B = Inte(Mul(Diff(arr), Inv(arr, n)));
        B.resize(n);
        return B;
    }

    inline poly Exp(poly arr, int n) {
        if(n == 1)
            return poly(1, 1);
        poly A = Exp(arr, (n + 1) >> 1);
        A.resize(n);
        poly B = Ln(A, n);
        for(int i = 0; i < n; i++)
            B[i] = (arr[i] - B[i] + mod) % mod;
        const int len = initrev(n << 1);
        NTT(A, len, 1);
        NTT(B, len, 1);
        for(int i = 0; i < len; i++) {
            A[i] = A[i] * (1 + B[i]) % mod;
        }
        NTT(A, len, 0);
        A.resize(n);
        return A;
    }
}

using namespace Polynomial;

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);

    poly A;
    A.clear();
    A.resize(n + 1);
    for(int u : arr) {
        A[u] = power(u, mod - 2) * power(m, u - 1) % mod;
    }

    A = Exp(A, n + 1);

    return A[n] * fac[n] % mod;
}

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;
    }
}