#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
char ud(char c, bool isU, int k) {
    if (isU) {
        c++;
        if (c >= 'a' + k) c -= k;
    } else {
        c--;
        if (c < 'a') c += k;
    }
    return c;
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int ttt;
    cin >> ttt;
    while (ttt--) {
        int n, k;
        cin >> n >> k;
        string s;
        cin >> s;
        vector<string> dp;
        string temp = "";
        dp.push_back(temp);
        for (int i = 0; i < n; i++) {
            temp.push_back('z');
            dp.push_back(temp);
        }
        for (int i = 0; i < n; i++) {
            //cout << dp[i] << endl;
            string temp = dp[i];
            temp.push_back(ud(s[i], true, k));
            if (temp.compare(dp[i + 1]) < 0) {
                dp[i + 1] = temp;
            }
            temp.pop_back();
            temp.push_back(ud(s[i], false, k));
            if (temp.compare(dp[i + 1]) < 0) {
                dp[i + 1] = temp;
            }
            temp.pop_back();
            if (i) {
                temp.push_back(s[i]);
                swap(temp[i], temp[i - 1]);
                if (temp.compare(dp[i + 1]) < 0) {
                    dp[i + 1] = temp;
                }
                temp = dp[i];
            }
            if (i < n - 1) {
                if (i > 0) {
                    //cout << temp << endl;
                    temp.push_back(s[i]);
                    temp.push_back(s[i + 1]);
                    swap(temp[i], temp[i + 1]);
                    swap(temp[i], temp[i - 1]);
                    //cout << i << temp << endl;
                    if (temp.compare(dp[i + 2]) < 0) {
                        dp[i + 2] = temp;
                    }
                }
                temp = dp[i];
                temp.push_back(ud(s[i + 1], true, k));
                temp.push_back(s[i]);
                if (temp.compare(dp[i + 2]) < 0) {
                    dp[i + 2] = temp;
                }
                temp = dp[i];
                temp.push_back(ud(s[i + 1], false, k));
                temp.push_back(s[i]);
                if (temp.compare(dp[i + 2]) < 0) {
                    dp[i + 2] = temp;
                }
                temp = dp[i];

                temp.push_back(s[i]);
                temp.push_back(s[i + 1]);
                if (temp.compare(dp[i + 2]) < 0) {
                    dp[i + 2] = temp;
                }
            }
            if (i == 0 || i == n - 1) {
                temp = dp[i];
                temp.push_back(s[i]);
                if (temp.compare(dp[i + 1]) < 0) {
                    dp[i + 1] = temp;
                }
            }
        }
        cout << dp[n] << endl;
    }
    return 0;
}