# include<bits/stdc++.h>
using namespace std;
# define l long long 
# define db double 
# define rep(i,a,b) for(l i=a;i<b;i++)
# define vi vector<l>
# define vvi vector<vi>
# define vsi vector<set<l> >
# define pb push_back
# define mp make_pair
# define ss second
# define ff first
# define pii pair<l,l>
# define trvi(v,it) for(vi::iterator it=v.begin();it!=v.end();++it)
# define read(a) freopen(a,"r",stdin)
# define write(a) freopen(a,"w",stdout)
# define io ios::sync_with_stdio(false)

#define ai(n) array<l,n>


const l MOD=1e9+7;
const l N=505;
const l INF=1e12;

l n,k;
string s;



char up(char c) {
	l cnt=c-'a';
	cnt=(cnt+1)%k;
	return 'a'+cnt;
}

char down(char c) {
	l cnt=c-'a';
	cnt=(cnt-1)%k;
	if(cnt<0) {
		cnt+=k;
	}
	return 'a'+cnt;
}

void solve() {
	cin>>n>>k;
	cin>>s;
	vector<string> dp(n+1), dp_gap(n+1);
	rep(i,0,n) {
		dp[i+1]=dp[i]+up(s[i]);
		// dp[i+1]=min(dp[i+1],dp[i]+up(s[i]));
		dp[i+1]=min(dp[i+1],dp[i]+down(s[i]));
		dp[i+1]=min(dp[i+1],dp[i]+s[i]);
		if(i>=1) {
			dp[i+1]=min(dp[i+1], dp[i].substr(0,i-1)+s[i]+dp[i].back());
		}
		dp_gap[i+1] = dp[i] + s[i];

		if(i>=1) {
			dp[i+1]=min(dp[i+1], dp_gap[i].substr(0,i-1) + s[i] + dp_gap[i].substr(i-1));
			dp[i+1]=min(dp[i+1], dp_gap[i].substr(0,i-1) + up(s[i]) + dp_gap[i].substr(i-1));
			dp[i+1]=min(dp[i+1], dp_gap[i].substr(0,i-1) + down(s[i]) + dp_gap[i].substr(i-1));
			dp[i+1]=min(dp[i+1], dp_gap[i] + s[i]);
		}
		if(i>=2) {
			dp[i+1] = min(dp[i+1], dp_gap[i].substr(0,i-2)+s[i]+dp_gap[i].substr(i-2));
		}
	}
	cout<<dp[n]<<"\n";
	return;
}


int main(){
	io;
	int t;
	cin >> t;
	rep(i,0,t) {
		solve();
	}

	return 0;
}