A string s₀ is given, only consisting of 0 and 1. The j-th character of the string s_i is s_i,j , when the index starts from 0. We defifine s_i (i ≥ 1) as follows:

The length of s_i is less than the length of s_i−1 by 1. And for each letter s_i,j in the string s_i ,

s_i,j = max(s_i−1,j , s_i−1,j+1).

For example, if s₀ = 1010, then s₁ = 111, s₂ = 11, etc.

f(s) represents the number of 1 in the string s. Please print the result of .

输入描述:

The fifirst line contains one integer t(1 ≤ t ≤ 105 ) — the number of test cases.
The fifirst line of each test case contains two integers n, and k (1 ≤ n ≤ 3 · 105 , 1 ≤ k ≤ n) — the length of s0 and the variable in .
The second line contains the string s0 — the original string mentioned above.
It is guaranteed that the sum of n over all test cases does not exceed 3 · 105 .

输出描述:

For each test case print one integer — the result of .

3
4 3
0011
4 2
0011
4 1
0011

7
6
4