B. Diverse String
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The diversity of a binary string $$$s$$$ is the number of distinct$$$^{\text{∗}}$$$ strings that can be obtained by performing the following operation at most once:

Choose an integer $$$0 \leq x \leq 1$$$ and two integers $$$1 \leq l \leq r \leq n$$$, and set $$$s_i := x$$$ for all $$$l \leq i \leq r$$$.

For example, the string 10 has diversity $$$3$$$ because the strings 10, 11, and 00. can be obtained.

You are given a string $$$s$$$ of length $$$n$$$ as well as an integer $$$k$$$. You are allowed to toggle the values of at most $$$k$$$ characters in the string. Your task is to determine the maximum possible diversity of the resulting string.

$$$^{\text{∗}}$$$Two strings $$$a$$$ and $$$b$$$ are distinct if there exists an index $$$i$$$ such that $$$a_i \neq b_i$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$0 \leq k \leq n$$$) — the length of the string and the maximum number of characters you are allowed to toggle.

The second line of each test case contains a binary string $$$s$$$ of length $$$n$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output

For each test case, output a line with a single integer — the maximum possible diversity of the string after toggling at most $$$k$$$ characters.

Example
Input
4
1 1
0
4 4
1001
5 1
11111
7 2
1101001
Output
2
11
16
23
Note

In the first test case, it is optimal to toggle the first character, resulting in the string 1 with a diversity of $$$2$$$.

In the second test case, the string 1111 achieves the maximum possible diversity of $$$11$$$.