G. Che Forest
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a string $$$s$$$ of length $$$n$$$. You are performing the following operations $$$k$$$ times:

  • choose a character $$$s_i$$$ ($$$1 \le i \le n$$$) and move it to the front of the string.
  • choose a character $$$s_i$$$ ($$$1 \le i \le n$$$) and move it to the back of the string.
  • choose a character $$$s_i$$$ ($$$1 \le i \le n$$$) and move it to the front of the string.
  • and so on, depending on the parity of the number of the operation.

Find the lexicographically smallest string you can obtain.

Input

The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 2 \cdot 10^5$$$).

The second line contains the string $$$s$$$, consisting of $$$n$$$ lowercase English letters.

The sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output the lexicographically smallest string you can obtain.

Example
Input
4
7 3
abacaba
9 2
theforces
5 4
edcba
7 3
pavlekn
Output
aaaacbb
cheforest
abcde
aeplknv
Note

In the first test case, we can do the following operations:

  • $$$abac\color{red}{a}ba$$$ $$$\rightarrow$$$ $$$\color{red}{a}abacba$$$
  • $$$aa\color{red}{b}acba$$$ $$$\rightarrow$$$ $$$aaacba\color{red}{b}$$$
  • $$$aaacb\color{red}{a}b$$$ $$$\rightarrow$$$ $$$\color{red}{a}aaacbb$$$

In the second test case, we can do the following operations:

  • $$$thefor\color{red}{c}es$$$ $$$\rightarrow$$$ $$$\color{red}{c}thefores$$$
  • $$$c\color{red}{t}hefores$$$ $$$\rightarrow$$$ $$$chefores\color{red}{t}$$$