Bessie discovered a new function that the entire herd can apply to its character strings.

Given both a number $N$ $1 \le N \le 15$ and a string $S$, with length strictly greater than $N$, define f$(N,S)$ as a new string composed of the concatenation of the substring from character $N$ (zero based -- first character is number 0) through the end of $S$ and the string $S$ itself.

For example, with $N = 2$, and $S$ = "COW", f$(N,S)$ = "$W$" + "COW" = "WCOW". Also, f(3, "USACO") = "CO" + "USACO" = "COUSACO".

Bessie is enthralled with this function and wants to iterate it several times. For example, if she iterates the function once for "COW" and $N = 2$, she will get "WCOW". If she applies the function with $N = 2$ again to that string, she will get "OWWCOW", and if she applies it one more time with $N = 2$, she will get "WCOWOWWCOW".

Help Bessie encode a total of $Z$ $1 \le Z \le 100$ strings, $str_1$, $str_2$, and so on. Each $str_i$ has length in the range 2..100 and contains only upper case letters. Each string is presented with its own $N_{i}$ ($0 \le N_{i} < \operatorname{length}(str_i)$, and iteration count $C_{i}$ $1 \le C_{i} \le 12$.

Input

• Line 1: A single integer: $Z$

• Lines $2..Z+1$: Line i+1 contains two space-separated integers, a space, and string to be encoded: $N_{i}$, $C_{i}$, and $str_i$

Output

• Lines $1,\ldots,Q$: Line j contains the iterated, encoded version of $str_j$

Examples

Input 1

2
2 3 COW
3 2 USACO

Output 1

WCOWOWWCOW
SACOCOUSACO

The arrow denotes an iteration of the function COW -> WCOW -> OWWCOW -> WCOWOWWCOW USACO -> COUSACO -> SACOCOUSACO

Problem credits: Lewin Gan, 2011