Little Mocha is a genius, especially with an extraordinary talent for string theory. To celebrate her talent, people often name strings that satisfy certain elegant properties "Mocha strings."

Description

Little H has a binary string $s$ of length $n$ and a positive integer $k$. He defines a binary string $t = t_1 \dots t_m$ of length $m$ as a "Mocha string" if and only if $t$ satisfies the following two conditions: $s$ is a substring of $t$, i.e., there exists $1 \le l \le r \le m$ such that $s = t_l \dots t_r$; There are exactly $k$ substrings of $t$ that are lexicographically strictly smaller than $s$. Two substrings are considered different if and only if they have different lengths or different starting positions. Formally, there are exactly $k$ pairs $(l, r)$ such that $1 \le l \le r \le m$ and the substring $t_l \dots t_r$ is lexicographically strictly smaller than $s$.

Since there may be many Mocha strings that satisfy these conditions, Little H wants to find one with the shortest length. You need to help him find any one of them.

Input

The input is read from the file string.in.

This problem contains multiple test cases. The first line contains two non-negative integers $c$ and $t$, representing the test case ID and the number of test cases, respectively. $c = 0$ indicates that this test case is a sample.

Following this, each test case is provided: The first line contains two positive integers $n$ and $k$. The second line contains a binary string $s$ of length $n$.

Output

The output is written to the file string.out.

For each test case, output a single line containing a binary string, representing any Mocha string of the shortest length. In particular, if no such Mocha string exists, output Impossible.

Examples

Input 1

0 5
1 1
1 1
1 1
3 9
101
4 17
1100
4 20
1100

Output 1

10
Impossible
0101
011100
001100

Example 2

See string/string2.in and string/string2.ans in the contestant's directory. This sample satisfies the constraints for test cases 4–6.

Example 3

See string/string3.in and string/string3.ans in the contestant's directory. This sample satisfies the constraints for test cases 7–9.

Example 4

See string/string4.in and string/string4.ans in the contestant's directory. This sample satisfies the constraints for test cases 10–12.

Example 5

See string/string5.in and string/string5.ans in the contestant's directory. This sample satisfies the constraints for test cases 13–15.

Example 6

See string/string6.in and string/string6.ans in the contestant's directory. This sample satisfies the constraints for test cases 16–18.

Example 7

See string/string7.in and string/string7.ans in the contestant's directory. This sample satisfies the constraints for test cases 19, 20.

Constraints

For all test cases: $1 \le t \le 5$; $1 \le n \le 200$, $1 \le k \le 3,000$; * For all $1 \le i \le n$, $s_i \in \{0, 1\}$.

Special Property A: If a Mocha string exists, there exists a Mocha string with length at most 15. Special Property B: For all $1 \le i \le n$, $s_i = 0$. Special Property C: For all $1 \le i \le n$, $s_i = 1$. Special Property D: There exists a positive integer $p \in [1, n]$ such that $s_1 = \dots = s_p = 0$ and $s_{p+1} = \dots = s_n = 1$.