#include<iostream>
#include<string>//the sourse of string
#include <algorithm>//the sourse of swap
#define N1 510
#define min(a,b) (a<b?a:b)
using namespace std;
int n,k;
string str,ans;//the definition of a string type
char D(char c)
{
	return 'a'+((c-'a')-1+k)%k;
}
char U(char c)
{
	return 'a'+((c-'a')+1)%k;
}
char best(char c)
{
	return min(c,min(D(c),U(c)));
}
int main()
{
	int t,idx,res;
	char pre;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&k);
		cin>>str;
		ans="";
		idx=0;
		while(idx<n)
		{
			ans+=str[idx];//the plus of string
			if(idx>=1)
			{
				pre=ans[idx-1];
				res=0;
				if(ans[idx]<ans[idx-1])
				{
					ans[idx-1]=ans[idx];
					res=1;
				}
				if(idx<n-1&&str[idx+1]<ans[idx-1])
				{
					ans[idx-1]=str[idx+1];
					ans+=str[idx];
					res=2;
				}
				if(res)
					ans[idx]=pre;
				if(res==1)
				{
					idx++;
					continue;
				}
				else if(res==2)
				{
					idx+=2;
					continue;
				}
			}
			ans[idx]=best(ans[idx]);
			res=0;
			if(idx+1<n&&best(str[idx+1])<ans[idx])
			{
				if(best(str[idx+1])==str[idx+1])
				{
					ans+=str[idx+1];
					swap(ans[idx],ans[idx+1]);
				}
				else
				{
					ans[idx]=best(str[idx+1]);
					ans+=str[idx];
				}
				res=1;
			}
			if(idx<n-2&&str[idx+2]<ans[idx])
			{
				while(ans.length()<idx+3)
					ans+='a';
				ans[idx]=str[idx+2];
				ans[idx+1]=best(str[idx]);
				ans[idx+2]=str[idx+1];
				res=2;
			}
			if(res==0)
				idx++;
			else if(res==1)
				idx+=2;
			else
				idx+=3;
		}
		cout<<ans<<endl;
	}	
	return 0;
}
