说明

时间限制：1 Sec 内存限制：256 MB 输入文件：sun.in 输出文件：sun.out

为了研究人造太阳（核聚变），小明考上了中科院的博士。他的第一项工作是协助完成实验。

实验装置是一条直线，在直线上有间隔为 $1$ 的 $n$ 个位置，反应堆只能安放在这 $n$ 个位置上，一开始已经有一些位置安放了反应堆。

由于反应堆的磁束缚力场会互相干扰，相邻的两个反应堆之间应该至少要隔开 $k$ 个位置。也就是说，如果位置 $p$ 安放了一个反应堆，那么它的左侧，位置 $p-1$、$p-2$、……、$p-k$ 都不能安放反应堆，$p-k-1$ 才可以安放。同理，它的右侧，位置 $p+1$、$p+2$、……、$p+k$ 都不能安放反应堆，$p+k+1$ 才可以安放。

现在小明的任务是根据已经安放的反应堆的情况，计算最多还能再安放多少个反应堆。请你写程序帮帮他。

输入格式

第一行为一个整数 $t$，表示有 $t$ 组询问。

接下来为 $t$ 组询问，每组询问包括两行，第一行为一个整数 $k$，第二行为一个长度为 $n$ 的01串 $s$，$s$ 中字符的序号表示对应位置上的反应堆，为 $0$ 表示没有反应堆，为 $1$ 表示有反应堆。

输出格式

$t$ 行，第 $i$ 为对第 $i$ 组询问的回答，为一个整数，表示最多还能安放多少个反应堆。

样例

样例 1

5
1
00100010
1
10101
1
001
2
00100
3
00001000

2
0
1
0
1

样例说明：以第 $1$ 组询问为例：

输入的位置与反应堆情况：00100010

标红的表示可以放的$1$，确保所有反应堆的间距不小于 $1$：10101010

所以答案为 $2$。

数据范围

$1 \le t \le 10^4$

$1 \le k \le n \le 2 \times 10^5$

题目保证所有 $n$ 之和不超过 $2 \times 10^5$