I. 小黑的鸡脚plus
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

题目背景同小黑的鸡脚。

给定长度为 n 的 01串 S，你可以将不超过 k 个 0 变为 1，请问最多可以取出多少个不相交的 完美d串。

完美d串 指长度为 d ，并且全为1的连续串。例如，完美3串就是指 111，完美5串指 11111。

Input

第一行一个整数 T。表示测试数据组数。

接下来 T 行，每行包含2个整数k, d，以及一个01字符串 S。

数据保证 0 ≤ k ≤ 100, 1 ≤ d ≤ 50, len(S) ≤ 2000, T ≤ 150

Output

输出 T 行，每行一个整数，代表可以取出最多的完美 d 串的数量。

Example
Input
3
0 3 11101111
1 4 10111111
2 4 10111101
Output
2
2
2