Problem: You are given a string s consisting of n characters. These characters are among the first k lowercase letters of the Latin alphabet. You have to perform n operations with the string.

During the i-th operation, you take the character that initially occupied the i-th position, and perform one of the following actions with it:

  * swap it with the previous character in the string (if it exists). This operation is represented as L; 
  * swap it with the next character in the string (if it exists). This operation is represented as R; 
  * cyclically change it to the previous character in the alphabet (b becomes a, c becomes b, and so on; a becomes the k-th letter of the Latin alphabet). This operation is represented as D; 
  * cyclically change it to the next character in the alphabet (a becomes b, b becomes c, and so on; the k-th letter of the Latin alphabet becomes a). This operation is represented as U; 
  * do nothing. This operation is represented as 0. 



For example, suppose the initial string is test, k = 20, and the sequence of operations is URLD. Then the string is transformed as follows:

  1. the first operation is U, so we change the underlined letter in test to the next one in the first 20 Latin letters, which is a. The string is now aest; 
  2. the second operation is R, so we swap the underlined letter with the next one in the string aest. The string is now aset; 
  3. the third operation is L, so we swap the underlined letter with the previous one in the string aset (note that this is now the 2-nd character of the string, but it was initially the 3-rd one, so the 3-rd operation is performed to it). The resulting string is saet; 
  4. the fourth operation is D, so we change the underlined letter in saet to the previous one in the first 20 Latin letters, which is s. The string is now saes. 



The result of performing the sequence of operations is saes.

Given the string s and the value of k, find the lexicographically smallest string that can be obtained after applying a sequence of operations to s.

Input

The first line contains one integer t (1 ≤ t ≤ 1000) — the number of test cases.

Each test case consists of two lines. The first line contains two integers n and k (1 ≤ n ≤ 500; 2 ≤ k ≤ 26). 

The second line contains a string s consisting of n characters. Each character is one of the k first letters of the Latin alphabet (in lower case).

Output

For each test case, print one line containing the lexicographically smallest string that can be obtained from s using one sequence of operations.

Example

Input


6
4 2
bbab
7 5
cceddda
6 5
ecdaed
7 4
dcdbdaa
8 3
ccabbaca
5 7
eabba


Output


aaaa
baccacd
aabdac
aabacad
aaaaaaaa
abadb

Solution (in CPP):

Solution:
#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

*/