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:
For example, suppose the initial string is test, $$$k = 20$$$, and the sequence of operations is URLD. Then the string is transformed as follows:
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$$$.
The first line contains one integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.
Each test case consists of two lines. The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 500$$$; $$$2 \le k \le 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).
For each test case, print one line containing the lexicographically smallest string that can be obtained from $$$s$$$ using one sequence of operations.
6 4 2 bbab 7 5 cceddda 6 5 ecdaed 7 4 dcdbdaa 8 3 ccabbaca 5 7 eabba
aaaa baccacd aabdac aabacad aaaaaaaa abadb