#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
    cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t << " | ";
    dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                           \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
         << ": ";                                          \
    dbgh(__VA_ARGS__)
#else
#define cerr   \
    if (false) \
    cerr
#define dbg(...)
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))

struct mint {
    static constexpr int MOD = 998244353;

    static constexpr int norm(long x) {
        x %= MOD;
        if (x < 0) {
            x += MOD;
        }
        return int(x);
    }

    static constexpr mint pow(mint base, long exp) {
        mint ans = 1;
        while (exp) {
            if (exp & 1) {
                ans *= base;
            }
            base *= base;
            exp >>= 1;
        }
        return ans;
    }

    static constexpr mint inv(mint base) {
        return pow(base, MOD - 2);
    }

    int x;

    constexpr mint() : x(0) {}
    constexpr mint(long x) : x(norm(x)) {}

    friend ostream& operator<<(ostream& out, const mint& m) {
        return out << m.x;
    }

    mint& operator+=(const mint& m) {
        x += m.x;
        if (x >= MOD) {
            x -= MOD;
        }
        return *this;
    }

    mint& operator*=(const mint& m) {
        x = int(long(x) * m.x % MOD);
        return *this;
    }
    mint& operator/=(const mint& m) {
        return *this *= inv(m);
    }

    friend mint operator+(mint a, const mint& b) {
        return a += b;
    }
    friend mint operator*(mint a, const mint& b) {
        return a *= b;
    }
    friend mint operator/(mint a, const mint& b) {
        return a /= b;
    }
};

struct M {
    static constexpr int maxn = 1e4;

    mint fact[maxn], ifact[maxn];

    M() {
        fact[0] = ifact[0] = 1;
        for (int i = 1; i < maxn; i++) {
            fact[i] = i * fact[i - 1];
            ifact[i] = mint::inv(fact[i]);
        }
    }

    mint choose(int n, int k) {
        return fact[n] * ifact[n - k] * ifact[k];
    }
} M;

mint solve(int len, int m, const vector<int>& arr) {
    if (!m) {
        return 1;
    }
    mint dp[m + 1];
    dp[m] = 1;
    for (int i = m - 1; i >= 0; i--) {
        for (auto& a : arr) {
            if (i + a <= m) {
                dp[i] += M.choose(m - i - 1, a - 1) * M.fact[a - 1] *
                         mint::pow(len, a - 1) * dp[i + a];
            }
        }
    }
    return dp[0];
}

void solve() {
    int n, kv;
    cin >> n >> kv;
    int iarr[n];
    for (auto& a : iarr) {
        cin >> a;
        a--;
    }
    int comps[n + 1] {};
    bool vis[n] {};
    for (int i = 0; i < n; i++) {
        if (vis[i]) {
            continue;
        }
        int u = i, cnt = 0;
        while (!vis[u]) {
            vis[u] = true;
            u = iarr[u];
            cnt++;
        }
        comps[cnt]++;
    }
    vector<int> clens[n + 1];
    for (int i = 1; i <= n; i++) {
        int g = gcd(i, kv);
        clens[i / g].push_back(g);
    }
    mint ans = 1;
    for (int i = 1; i <= n; i++) {
        int m = comps[i];
        auto& arr = clens[i];
        ans *= solve(i, m, arr);
    }
    cout << ans << endl;
}

int main() {
    cin.tie(nullptr);
    cin.exceptions(ios::failbit);
    ios_base::sync_with_stdio(false);
    int tcs;
    cin >> tcs;
    while (tcs--) {
        solve();
    }
}