#include <bits/stdc++.h>

using namespace std;

const int MOD = 998244353;

int add(int x, int y) {
    x += y;
    if (x >= MOD) x -= MOD;
    return x;
}

int sub(int x, int y) {
    x -= y;
    if (x < 0) x += MOD;
    return x;
}

int mult(int x, int y) {
    return int64_t(x) * y % MOD;
}

int solve1(int N, string S) {
    vector<array<int, 26>> nxt(N + 1);
    nxt[N].fill(N + 1);
    for (int i = N - 1; i >= 0; --i) {
        nxt[i] = nxt[i + 1];
        nxt[i][S[i] - 'a'] = i + 1;
    }
    vector<int> dp(N + 1);
    for (int c = 0; c < 26; ++c) {
        if (nxt[0][c] <= N) {
            dp[nxt[0][c]] = add(dp[nxt[0][c]], 1);
        }
    }

    int ans = 0;
    for (int i = 1; i <= N; ++i) {
        char pc = S[i - 1] - 'a';
        if (nxt[i][pc] == N + 1) {
            ans = add(ans, dp[i]);
        }

        for (int c = 0; c < 26; ++c) {
            if (nxt[i][c] <= N && nxt[i][c] <= nxt[i][pc]) {
                dp[nxt[i][c]] = add(dp[nxt[i][c]], dp[i]);
            }
        }
    }
    return ans;
}

int solve2(int N, string S) {
    vector<array<int, 26>> nxt(N + 1);
    nxt[N].fill(N + 1);
    for (int i = N - 1; i >= 0; --i) {
        nxt[i] = nxt[i + 1];
        nxt[i][S[i] - 'a'] = i + 1;
    }
    array<int, 26> last{};
    vector<int> prv(N + 1);
    for (int i = 0; i < N; ++i) {
        prv[i + 1] = last[S[i] - 'a'];
        last[S[i] - 'a'] = i + 1;
    }
    vector<array<int, 3>> dp(N + 1);
    for (int c = 0; c < 26; ++c) {
        int i = nxt[0][c];
        if (i <= N) {
            dp[i][0] = add(dp[i][0], 1);
            if (nxt[i][c] <= N) {
                dp[nxt[i][c]][1] = add(dp[nxt[i][c]][1], 1);
            }
        }
    }

    int ans = 0;
    for (int i = 1; i <= N; ++i) {
        // cerr << dp[i][0] << ' ' << dp[i][1] << ' ' << dp[i][2] << '\n';
        int pc = S[i - 1] - 'a';
        if (nxt[i][pc] == N + 1) {
            ans = add(ans, dp[i][1]);
            ans = add(ans, dp[i][2]);
        }

        // 0 -> 0
        // 2 -> 2
        for (int c = 0; c < 26; ++c) {
            if (nxt[i][c] <= N && nxt[i][c] <= nxt[i][pc]) {
                dp[nxt[i][c]][0] = add(dp[nxt[i][c]][0], dp[i][0]);
                dp[nxt[i][c]][2] = add(dp[nxt[i][c]][2], dp[i][2]);
            }
        }

        // 0 -> 1
        for (int c = 0; c < 26; ++c) {
            if (c == pc) continue;
            int ni = nxt[i][c];
            if (ni == N + 1) continue;
            int nni = nxt[ni][c];
            if (nni == N + 1) continue;
            if (nxt[i][pc] <= nni) continue;
            dp[nni][1] = add(dp[nni][1], dp[i][0]);
        }

        // 1 -> 2
        int pi = prv[i];
        if (pi == 0) continue;
        for (int c = 0; c < 26; ++c) {
            if (c == pc) continue;
            if (nxt[pi][c] == nxt[i][c] && nxt[i][c] <= nxt[i][pc] && nxt[i][c] <= N) {
                dp[nxt[i][c]][2] = add(dp[nxt[i][c]][2], dp[i][1]);
            }
        }
    }
    return ans;
}

int brute(int K, int N, string S) {
    unordered_map<string, int> cnt;
    for (int mask = 0; mask < (1 << N); ++mask) {
        string T;
        for (int i = 0; i < N; ++i) if (mask >> i & 1) {
            T += S[i];
        }
        cnt[T]++;
    }
    int ans = 0;
    for (auto [s, f] : cnt) {
        if (f == K) ans++;
    }
    return ans;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);

    int T, K; cin >> T >> K;
    while (T--) {
        int N; string S; cin >> N >> S;
        if (K == 1) {
            cout << solve1(N, S) << '\n';
        } else {
            cout << solve2(N, S) << '\n';
        }
    }
    return 0;
}

// ababab