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>
#define fi first
#define se second
#define o2(x) (x) * (x)
#define mk make_pair
#define eb emplace_back
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define clr(a, b) memset((a), (b), sizeof((a)))
#define rep(i, s, t) for(register int i = (s), LIM=(t); i < LIM; ++i)
#define per(i, s, t) for(register int i = (s), LIM=(t); i >= LIM; --i)
#define GKD std::ios::sync_with_stdio(false);cin.tie(0)
#define my_unique(x) sort(all(x)), x.erase(unique(all(x)), x.end())
using namespace std;
typedef long long LL;
typedef long long int64;
typedef unsigned long long uint64;
typedef pair<int, int> pii;
// mt19937 rng(time(NULL));//std::clock()
// mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());
// shuffle(arr, arr + n, rng64);
inline int64 read() {
    int64 x = 0;int f = 0;char ch = getchar();
    while (ch < '0' || ch > '9') f |= (ch == '-'), ch = getchar();
    while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch =
    getchar(); return x = f ? -x : x;
}
inline void write(int64 x, bool f = true) {
    if (x == 0) {putchar('0'); if(f)putchar('\n');else putchar(' ');return;}
    if (x < 0) {putchar('-');x = -x;}
    static char s[23];
    int l = 0;
    while (x != 0)s[l++] = x % 10 + 48, x /= 10;
    while (l)putchar(s[--l]);
    if(f)putchar('\n');else putchar(' ');
}
int lowbit(int x) { return x & (-x); }
template <class T>
T big(const T &a1, const T &a2) {return a1 > a2 ? a1 : a2;}
template <class T>
T sml(const T &a1, const T &a2) {return a1 < a2 ? a1 : a2;}
template <typename T, typename... R>
T big(const T &f, const R &... r) {return big(f, big(r...));}
template <typename T, typename... R>
T sml(const T &f, const R &... r) {return sml(f, sml(r...));}
void debug_out() { cout << '\n'; }
template <typename T, typename... R>
void debug_out(const T &f, const R &... r) {
    cout << f << " ";
    debug_out(r...);
}
#ifdef LH_LOCAL
#define debug(...) cout << "[" << #__VA_ARGS__ << "]: ", debug_out(__VA_ARGS__);
#else
#define debug(...) ;
#endif
/*================Header Template==============*/
const int mod = 998244353;// 998244353
int ksm(int a, int64 b, int kmod = mod) {int res = 1;for(;b > 0;b >>= 1, a = (int64)a * a % kmod) if(b &1) res = (int64)res * a % kmod;return res;}
const int INF = 0x3f3f3f3f;
const int MXN = 2e5 + 5;

int n, m;
char s[MXN];
int ori[MXN], dwn[MXN];
/*
origin[i] 表示i位置的字符是否原本就在i。
down[i] 表示i位置的字符能否循环移动。
如果i+1的字符能移动到i，需要保证i+1原本就在i+1。
如果i+2的字符能移动到i，需要保证i+1原本就在i+1。
如果经过合法改变后，从i来的字符是最小的就选i位置保持不变，否则如果从i+1来的字符是最小的就选i+1位置，否则如果从i+2来的字符是最小的就选i+2位置，否则就不变。
*/
void work() {
    n = read(), m = read();
    rep(i, 0, n) ori[i] = dwn[i] = 0;
    scanf("%s", s);
    rep(i, 0, n) {
        int a = s[i] - 'a', b = (i + 1 < n && ori[i + 1] == 0? s[i + 1] - 'a': INF), c = (i + 2 < n && ori[i + 1] == 0? s[i + 2] - 'a': INF);
        //位置i可以循环移动
        if(dwn[i] == 0) a = sml(a, (a + 1) % m, (a + m - 1) % m);
        //位置i+1可以循环移动
        if(b != INF && ori[i] == 0 && dwn[i + 1] == 0 && ori[i + 1] == 0) b = sml(b, (b + 1) % m, (b + m - 1) % m);
        if(a <= b && a <= c) {
            s[i] = a + 'a';
        }else if(b <= a && b <= c) {
            swap(s[i], s[i + 1]);
            if(s[i] != b + 'a') {//这时候i要必须先做操作R，所以改变后i+1没法循环移动
                s[i] = b + 'a';
                dwn[i + 1] = 1;
            }else {
                //这时候i+1位置是不需要经过循环移动来变成更小的元素的，所以i位置是可能保留了一次操作，先不要急着操作，后面再慢慢考虑。
            }
            if(dwn[i]) dwn[i + 1] = 1;//但是如果原本i本来就没法循环移动，那么改变后i+1也没法循环移动
            ori[i + 1] = 1;//i+1肯定不是原位置的啦
        }else if(c <= a && c <= b) {
            swap(s[i], s[i + 2]);
            swap(s[i + 1], s[i + 2]);
            //这时候其实i位是可能能保留了一次操作，先不要急着操作，后面再慢慢考虑。
            if(dwn[i]) dwn[i + 1] = 1;//但是如果原本i本来就没法循环移动，那么改变后i+1也没法循环移动
            ori[i + 1] = 1;//i+1肯定不是原位置的啦
            ori[i + 2] = dwn[i + 2] = 1;//原本i+1做了操作R，所以改变后肯定没法做循环移动操作，也不是原位置
        }
        // debug(i, s)
    }
    printf("%s\n", s);
}
int main() {
#ifdef LH_LOCAL
    freopen("D:/ACM/mtxt/in.txt", "r", stdin);
    // freopen("D:/ACM/mtxt/out.txt", "w", stdout);
#endif
    for(int cas = 1, tim = read(); cas <= tim; ++ cas) {
        // printf("Case #%d:\n", cas);
        work();
    }
#ifdef LH_LOCAL
    cout << "time cost:" << 1.0 * clock() / CLOCKS_PER_SEC << "s" << endl;
#endif
    return 0;
}