#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
typedef long long ll;
const int M = 510;
int T,n,k;
string s, dp[M];

int main(){
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> T;
	while(T--){
		cin >> n >> k >> s;
		dp[0] = "";
		for(int i = 1;i <= n; i++) dp[i] = (char)('z' + 1);
		for(int i = 0,ch,nc;i < n; i++){
			ch = s[i] - 'a', nc = min(ch,min((ch + 1) % k,(ch + k - 1) % k));
			dp[i + 1] = min(dp[i + 1], dp[i] + (char)('a' + nc));
			if(i > 0) 
				dp[i + 1] = min(dp[i + 1],dp[i - 1] + (char)('a' + nc) + s[i - 1]),
				dp[i + 1] = min(dp[i + 1],dp[i].substr(0, i - 1) + s[i] + dp[i][(int)dp[i].length() - 1]);
			if(i > 1)
				dp[i + 1] = min(dp[i + 1],dp[i - 1].substr(0, i - 2) + s[i] + dp[i - 1][(int)dp[i - 1].length() - 1] + s[i - 1]);
		}
		cout << dp[n] << endl;
	}
	return 0;
}