问题描述

Farmer John 正试图提高 United Cows of Farmer John（UCFJ）的识字率。UCFJ 由 ~n~ 块地和 ~\frac{n}{k}~ 个农场组成（其中 ~n~ 是 ~k~ 的倍数），每个农场由 ~k~ 块连续的地组成。换言之，第 ~i~ 块地属于第 ~\lceil \frac{i}{k} \rceil~ 个农场：第 ~1, 2, \ldots, k~ 块地属于第一个农场，第 ~k+1, k+2, \ldots, 2k~ 块地属于第二个农场，依此类推。

Farmer John 想要建造学校，使得每个农场至少有一所学校。然而，有些地属于 Farmer Nhoj，Farmer John 在这些地上建学校需要额外付费。Farmer John 想知道，为了保证每个农场至少有一所学校，他最少需要多少次在 Farmer Nhoj 的地上建学校。

输入

每个输入的第一行包含一个整数 ~t~（~1 \leq t \leq 10^4~）—— 测试用例的数量。

每个测试用例的第一行包含两个整数 ~n~ 和 ~k~（~1 \leq k \leq n \leq 20~，~n~ 是 ~k~ 的倍数）—— 地的数量与每个农场的大小。

每个测试用例的第二行包含一个长度为 ~n~ 的二进制字符串 ~s~ —— 属于 Farmer Nhoj 的地。若 ~s_i = 1~，则第 ~i~ 块地属于 Farmer Nhoj。若 ~s_i = 0~，则第 ~i~ 块地不属于 Farmer Nhoj。

输出

对于每个测试用例，输出一个整数 —— Farmer John 必须在 Farmer Nhoj 的地上建学校的最少次数。

样例输入

6
8 2
10011100
5 1
11111
8 4
01111110
5 1
00101
4 4
1101
4 4
1111

样例输出

1
5
0
2
0
1

说明

对于第一组测试用例，我们可以把学校建在第 ~2~、~3~、~5~、~7~ 块地上，其中只有第 ~5~ 块地属于 Farmer Nhoj，因此答案是 ~1~。可以证明这是最优答案。

对于第二组测试用例，Farmer Nhoj 拥有全部的地，由于必须建 ~5~ 所学校，所以必须在 Farmer Nhoj 的地上建 ~5~ 次。