#include<bits/stdc++.h>
using namespace std;
//typedef __int128 ll;
typedef long long ll;

typedef double db;
typedef pair<int, int> pii;typedef pair<ll, ll> pll;
typedef pair<int,ll> pil;typedef pair<ll,int> pli;
#define Fi first
#define Se second
#define _Out(a)	cerr<<#a<<" = "<<(a)<<endl
const int INF = 0x3f3f3f3f, MAXN = 1e6 + 5;
const ll LINF = 0x3f3f3f3f3f3f3f3f, MOD = 1e9+7;
const db Pi = acos(-1), EPS = 1e-6;
void test(){cerr << "\n";}template<typename T,typename...Args>void test(T x,Args...args){cerr<<x<<" ";test(args...);}
inline ll qpow(ll a, ll b){return b?((b&1)?a*qpow(a*a%MOD,b>>1)%MOD:qpow(a*a%MOD,b>>1))%MOD:1;}
inline ll qpow(ll a, ll b,ll c){return b?((b&1)?a*qpow(a*a%c,b>>1,c)%c:qpow(a*a%c,b>>1,c)) %c:1;}
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
inline ll cede(ll a,ll b){if(b<0)return cede(-a,-b);if(a<0)return a/b;return (a+b-1)/b;}
inline ll flde(ll a,ll b){if(b<0)return flde(-a,-b);if(a<0)return (a-b+1)/b;return a/b;}
inline int sign(db x){return x<-EPS ? -1:x>EPS;}
inline int dbcmp(db l,db r){return sign(l - r);}
namespace Fast_IO{ //orz laofu
    const int MAXL((1 << 18) + 1);int iof, iotp;
    char ioif[MAXL], *ioiS, *ioiT, ioof[MAXL],*iooS=ioof,*iooT=ioof+MAXL-1,ioc,iost[55];
    char Getchar(){
        if (ioiS == ioiT){
            ioiS=ioif;ioiT=ioiS+fread(ioif,1,MAXL,stdin);return (ioiS == ioiT ? EOF : *ioiS++);
        }else return (*ioiS++);
    }
    void Write(){fwrite(ioof,1,iooS-ioof,stdout);iooS=ioof;}
    void Putchar(char x){*iooS++ = x;if (iooS == iooT)Write();}
    inline int read(){
        int x=0;for(iof=1,ioc=Getchar();(ioc<'0'||ioc>'9')&&ioc!=EOF;)iof=ioc=='-'?-1:1,ioc=Getchar();
        if(ioc==EOF)Write(),exit(0);
        for(x=0;ioc<='9'&&ioc>='0';ioc=Getchar())x=(x<<3)+(x<<1)+(ioc^48);return x*iof;
    }
    inline long long read_ll(){
        long long x=0;for(iof=1,ioc=Getchar();(ioc<'0'||ioc>'9')&&ioc!=EOF;)iof=ioc=='-'?-1:1,ioc=Getchar();
        if(ioc==EOF)Write(),exit(0);
        for(x=0;ioc<='9'&&ioc>='0';ioc=Getchar())x=(x<<3)+(x<<1)+(ioc^48);return x*iof;
    }
    void Getstr(char *s, int &l){// isgraph || isalnum || iscntrl || isblank
        for(ioc=Getchar();ioc!=EOF&&!isgraph(ioc);)ioc=Getchar();
        if(ioc==EOF)Write(),exit(0);
        for(l=0;isgraph(ioc);ioc=Getchar())s[l++]=ioc;s[l] = 0;
    }
    template <class Int>void Print(Int x, char ch = '\0'){
        if(!x)Putchar('0');if(x<0)Putchar('-'),x=-x;while(x)iost[++iotp]=x%10+'0',x/=10;
        while(iotp)Putchar(iost[iotp--]);if (ch)Putchar(ch);
    }
    void Putstr(const char *s){for(int i=0;s[i];++i)Putchar(s[i]);}
} // namespace Fast_IO
using namespace Fast_IO;

char str[555];
int a[555],k,n;
bool dp[505][28][2];
int D(int v)
{
    return (v-2+k)%k+1;
}
int U(int v)
{
    return v%k+1;
}
bool QAQ;
int findminchar(int i,bool ok=0)
{
    int ans=a[i];
    QAQ=0;
    if(ok)ans=INF;
    for(int j=0;j<=26;j++)
    {
        if(dp[i-1][j][0])
        {
            ans=min(j,ans);
        }
        if(ok)continue;
        if(dp[i-1][j][1])
        {
            ans=min(ans,min(min(a[i],U(a[i])),D(a[i])));
            ans=min(ans,j);
        }
    }
    if(i<=n-1&&ans>a[i+1])QAQ=1,ans=a[i+1];
    return ans;
}
void work()
{
    memset(dp,0,sizeof dp);
    n=read();k=read();
    Getstr(str+1,n);
    for(int i=1;i<=n;i++)a[i]=str[i]-'a'+1;
    dp[0][0][0]=1;
    for(int i=1;i<=1+n;i++)
    {
        int minv=findminchar(i,i==n+1);
        if(minv)printf("%c",minv+'a'-1);
        if(QAQ)
        {
            for(int j=0;j<=k;j++)
            {
                if(dp[i-1][j][0])
                {
                    printf("%c",j+'a'-1);
                    break;
                }
            }
            dp[i+1][a[i]][0]=1;
            i++;
            continue;
        }
        if(i==n+1)break;
        for(int j=0;j<=k;j++)
        {
            if(dp[i-1][j][0])
            {
                if(j==minv)
                {
                    dp[i][U(a[i])][0]=1;
                    dp[i][D(a[i])][0]=1;
                    dp[i][a[i]][0]=1;
                    dp[i][a[i]][1]=1;
                }
                if(a[i]==minv)
                {
                    dp[i][j][0]=1;
                }
            }
            if(dp[i-1][j][1])
            {
                if(j==minv)
                {
                    dp[i][a[i]][0]=1;
                    
                }
                if(U(a[i])==minv||D(a[i])==minv)
                {
                    dp[i][j][0]=1;
                }
                if(a[i]==minv)
                {
                    dp[i][j][0]=1;
                }
            }
        }
    
    }
    printf("\n");
}
int main()
{
    //std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T=read();for(int cas=1;cas<=T;cas++)
    //int T;scanf("%d",&T);for(int i=1;i<=T;i++)
    work();
   //  Write();
}

/**
1
0 0
10 0
1 10
10 10


0 2
4 2
2 0
2 4
1 0
2 0
4 0
6 0


1
2 2
4 1
1 6
2 5

*/