SPOTIT - Spot the largest string

no tags 

 

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.

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^0)*1 + (2^1)*0 + (2^2)*1 + (2^3)*1 = 13

Input

 

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

T test case 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

N>=L

 

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.


Added by:Ishani Parekh
Date:2011-09-22
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own