C. Yet Another ÷2 or +1 Problem
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

For a string $$$t$$$ of length $$$m$$$,note:

$$$$$$f(t)=\begin{cases}t_1...t_mt_m,\quad\text{t is a palindrome}\\t_1...t_{\lfloor \frac{m}{2} \rfloor},\quad\text{Otherwise} \end{cases}$$$$$$

A palindrome is a string that reads the same forward and backward.

For a given string $$$s$$$ of length $$$n$$$ and a given number $$$k$$$,find $$$f(...f(f(s)))$$$($$$k$$$ times).

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n,k$$$ ($$$1\le n,k \le 10^{6}$$$).

The second line contains a string $$$s$$$ of length $$$n$$$ composed of lowercase letters.

The sum of $$$n,k$$$ over all test cases will not exceed $$$10^6$$$.

Output

For each test case, output on a new line — $$$f(...f(f(s)))$$$($$$k$$$ times).

Example
Input
3
2 2
ab
6 3
abaaba
8 3
cabsuixq
Output
aa
abaa
c
Note

Test Case $$$1$$$:

$$$f(f(ab))=f(a)=aa$$$.

Test Case $$$2$$$:

$$$f(f(f(abaaba)))=f(f(abaabaa))=f(aba)=abaa$$$.