#GYM104683C. Yet Another ÷2 or +1 Problem
Yet Another ÷2 or +1 Problem
Description
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).
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$.
For each test case, output on a new line — $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).
3
2 2
ab
6 3
abaaba
8 3
cabsuixq
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$.