#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define mp make_pair
#define fr first
#define sc second

int lg(ll n) {
    assert(n > 0);
    int ans = -1;
    while (n) {
        ans++;
        n >>= 1;
    }
    return ans;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        string s;
        cin >> s;
        assert(n == (int)s.length());

        vector<string> dp(n + 1);
        dp[0] = "";
        for (int i = 1; i <= n; i++) dp[i] = (char)('z' + 1);

        for (int i = 0; i < n; i++) {
            int ch = s[i] - 'a';
            int best = min({ch, (ch + 1) % k, (ch + k - 1) % k});
            dp[i + 1] = min(dp[i + 1], dp[i] + (char)(best + 'a'));  // U, D
            if (i > 0) {
                dp[i + 1] =
                    min(dp[i + 1], dp[i].substr(0, i - 1) + (char)(ch + 'a') +
                                       dp[i].back());  // L
                dp[i + 1] = min(dp[i + 1], dp[i - 1] + (char)(best + 'a') +
                                               s[i - 1]);  // RD, RU
            }
            if (i > 1) {  // RL
                dp[i + 1] = min(dp[i + 1], dp[i - 1].substr(0, i - 2) + s[i] +
                                               dp[i - 1].back() + s[i - 1]);
            }
        }

        cout << dp[n] << '\n';
    }

    return 0;
}
