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

long long t,n,k,pos;
string s;
bool mode;

char best(int pos){
	char c=s[pos];
	
	return min({c,char((c-'a'+1)%k+'a'),char(((c-'a'-1)%k+k)%k+'a')});
}

int main(){

	ios::sync_with_stdio(false);
	cin.tie(0);

	cin>>t;
	
	while(t--){
		cin>>n>>k>>s;
		
		mode=false;
		pos=0;
		
		while(pos<s.size()){
			if(mode==false){
				if((pos+1>=s.size() || best(pos)<= best(pos+1)) && (pos+2>=s.size() || best(pos)<=s[pos+2])){
					s[pos]=best(pos);
					pos++;
					mode=false;
				}else if(pos+2>=s.size() || best(pos+1)<=s[pos+2]){
					if(best(pos+1)==s[pos+1]){
						s[pos]=best(pos);
						swap(s[pos],s[pos+1]);
						pos++;
						mode=true;
					}else{
						s[pos+1]=best(pos+1);
						swap(s[pos],s[pos+1]);
						mode=true;
						pos++;
					}
				}else{
					s[pos]=best(pos);
					swap(s[pos+1],s[pos+2]);
					swap(s[pos],s[pos+1]);
					pos+=2;
					mode=true;
				}
			}else{
				if((pos+1>=s.size() || s[pos]<=s[pos+1]) && (pos+2>=s.size() || s[pos]<=s[pos+2])){
					pos++;
					mode=false;
				}else if(pos+2>=s.size() || s[pos+1]<=s[pos+2]){
					swap(s[pos],s[pos+1]);
					pos++;
					mode=true;
				}else{
					swap(s[pos+1],s[pos+2]);
					swap(s[pos],s[pos+1]);
					pos+=2;
					mode=true;
				}
			}
			
			//cout<<s<<"\n";
			//cout<<pos<<" "<<mode<<" ecco \n";
		}
		
		cout<<s<<"\n";
	}

	return 0;
}

