You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Time Limit: 1.0 s

Memory Limit: 256.0 MB

Description

You are given a binary string S of length N and a non-negative integer K.

You can perform the following operation at most K times:

• choose a substring of S and reverse it.

Your goal is to maximize the number of consecutive 1s in the final string after performing at most K operations.

Input

• The first line contains an integer T(1 ≤ T ≤ \(10^4\)), the number of test cases.
• For each test case:
• The first line contains two integers N and K (1 ≤ N ≤ 2 * \(10^5\), 0 ≤ K ≤ \(10^9\)).
• The second line contains a binary string S of length N. String contains only 0 and 1.
• Sum of N overall test cases doesn’t exceed 2 * \(10^5\).

Output

For each test case, output the maximum number of consecutive 1s that can be achieved.

Sample

3

7 1

1010011

7 0

0011011

6 2

100101

3

2

3