Table of Contents
Zebra Crossing Solution Codechef september cook off 2021
There’s a zebra crossing appearing in the middle of nowhere with NN blocks in it. The colors of the zebra crossing is represented by a binary string SS, where SiSi is 1
if the iith 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 whiteblack color pattern while crossing it.
Initially, Chef stands at block 11. Chef has to jump exactly KK 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 ii and wants to jump to block jj then following conditions should hold:
 i<ji<j
 Si≠SjSi≠Sj
Output the farthest block Chef can reach with exactly KK jumps. If Chef cannot jump exactly KK times, output 1
.
Input Format
 The first line contains an integer TT denoting the number of test cases. The TT test cases then follow.
 The first line of each test case contains two integers NN and KK.
 The second line of each test case consists of a binary string of length NN denoting the color of blocks of the zebra crossing.
Output Format
For each test case, output the farthest block Chef can reach with exactly KK jumps, or 1
in case Chef cannot jump exactly KK times.
Constraints
 1≤T≤1051≤T≤105
 2≤N≤1032≤N≤103
 1≤K≤N1≤K≤N
 Sum of NN over all test cases does not exceed 5⋅1055⋅105
Sample Input 1
3
6 2
100101
5 1
10111
6 1
000000
Sample Output 1
6
2
1
Explanation

For the first test case, Chef can jump in the following order: 1→5→61→5→6.

For the second test case, Chef can jump in the following order: 1→21→2.

For the third test case, Chef cannot make any jumps.