There’s a zebra crossing appearing in the middle of nowhere with
1 if the -th block from the left is white, and
0 if the block is black.
Chef really wants to play with the zebra crossing. Although the given zebra crossing might not have alternate black and white blocks, Chef wants to follow the alternating white-black color pattern while crossing it.
Initially, Chef stands at block. Chef has to jump exactly times, and in each jump he has to move forward and jump to a different color than that previously occupied by Chef. More formally, suppose that Chef is currently at block and wants to jump to block then following conditions should hold:
Output the farthest block Chef can reach with exactly
- The first line contains an integer denoting the number of test cases. The test cases then follow.
- The first line of each test case contains two integers and .
- The second line of each test case consists of a binary string of length denoting the color of blocks of the zebra crossing.
For each test case, output the farthest block Chef can reach with exactly
-1 in case Chef cannot jump exactly times.
- Sum of over all test cases does not exceed
Sample Input 1
3 6 2 100101 5 1 10111 6 1 000000
Sample Output 1
6 2 -1
For the first test case, Chef can jump in the following order:.
For the second test case, Chef can jump in the following order:.
For the third test case, Chef cannot make any jumps.