Rat Ronnie is very intelligent. Recently she got interested in the binary number system. Seeing this Rat Rocky decided to give her a problem to solve. If she solves it then she gets a big piece of cheese as a prize :).

A binary string of length N is a string that contains N characters. Each of these characters is either 0 or 1. Given a binary string S of length N and another input integer L, find a substring of length exactly L whose decimal value is largest amongst all substrings of length L in S. Print this largest value. (See notes and examples for further clarification)

Now Rat Ronnie is unable to think of anything else but cheese. As you are a brilliant programmer, she wants you to solve the problem. She promises to share the piece of cheese if you succeed.

Notes

• A substring of a string S, is any contiguous sequence of characters in the string. For example, "cde" is a substring of "abcdef" but "ce" is not a substring of "abcdef".

• A value of a binary substring is the value after converting it to a decimal number. For example- Decimal value of "1101" = 2⁰×1 + 2¹×0 + 2²×1 + 2³×1 = 13

Input

The first line is T, the number of test cases.

T test cases follows. The first line of every test case contains two integers N and L. The second line of every test case contains a binary string of length N.

1 ≤ T ≤ 100

1 ≤ N ≤ 100

1 ≤ L ≤ 50

L ≤ N

Output

Output the maximum decimal value of the substring of length L. As the output may be large, use an appropriate data type.

Example

Input:
3
7 3
0110111
5 3
10110
4 4
1000

Output:
7
6
8

Explanation of Example

In the second test case, possible substrings of length 3 are "101" , "011", "110" . Out of these, "110" has the highest value in decimal, i.e., 6.