N. hsq 的祭祖实验
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

可怜的 hsq 被通知周末连续两天上计组实验课 ， 但是他根本不会计组 。 计组实验的代码都是 克劳德先生 帮他完成的 。

等检查的时候 ， 老师问他 ： 这个七段数码管的显示原理是什么 ？ 译码器是怎么工作的 ？ 你现在显示的是 $$$1$$$ ， 我想显示 $$$2$$$ ， 你该怎么改输入 ？

hsq 当场就是一个投降 。 回到寝室后 ， 他痛定思痛 ， 开始研究数码管的显示效果 。

他发现 ， 实验板上的模块可以抽象成一个 $$$4n$$$ 位的移位寄存器 ， 寄存器中的信号每 $$$4$$$ 位被划分为一组 ， 作为一个二进制数 （ 规定高位在前 ， 例如 $$$0001$$$ 对应 $$$1$$$ ， $$$1000$$$ 对应 $$$8$$$ ， 转化后的十进制数字范围为 $$$0 \sim 15$$$ ） 输入到译码器中 ， 从而在 $$$n$$$ 个数码管上显示出 $$$n$$$ 个数字组成的数组 。

现在他有一串长度为 $$$4n$$$ 的环形二进制数据流 $$$S$$$ ， 但是他不知道应该从环上的哪个位置作为起始点 （ 即切口 ） 来拉直并读取这 $$$4n$$$ 位信号 。

他希望数据流解析完毕后 ， 能够在其解码出的 $$$n$$$ 个数字组成的数组中 ， 出现连续的子数组 $$$1, 2, 0$$$ （ 恰好他的寝室门牌号就是 $$$120$$$ ） 。

给定数据流 $$$S$$$ ， 请你帮他计算一下 ， 在所有的 $$$4n$$$ 个可能的起始点中 ， 有多少个起点解析出的数组包含至少一个连续的子数组 $$$1, 2, 0$$$ ？

Input

第一行包含一个正整数 $$$t$$$ ( $$$1 \le t \le 10^4$$$ ) ， 表示测试数据的组数 。

对于每组测试数据 ：

第一行包含一个正整数 $$$n$$$ ( $$$3 \le n \le 10^5$$$ ) ， 表示解码后的整数数组长度 。

第二行包含一个长度为 $$$4n$$$ 的 $$$01$$$ 字符串 $$$S$$$ ， 表示环形数据流 （ 输入以线性串的形式给出 ， 实际首尾相连构成环 ） 。

数据保证 ， 在所有的测试数据中 ， $$$n$$$ 的总和不超过 $$$10^5$$$ 。

Output

对于每组测试数据 ， 输出一行一个整数 ， 表示满足条件的起始点数量 。

Example
Input
2
3
000100100000
4
0001001000001111
Output
1
2
Note

在第一组测试数据中 ， 当起始点为 $$$0$$$ 时 ， 拉直后的字符串为 $$$000100100000$$$ ， 按 $$$4$$$ 位一组解码得到数组 $$$[ 1, 2, 0 ]$$$ ， 包含连续子数组 $$$1, 2, 0$$$ ， 因此是一个合法的起点 。

当起始点为 $$$1$$$ 时 ， 拉直后的字符串为 $$$001001000000$$$ ， 解码得到数组 $$$[ 2, 4, 0 ]$$$ ， 不包含连续子数组 $$$1, 2, 0$$$ ， 因此不是合法的起点 。

遍历所有 $$$12$$$ 个可能的起点 ， 最终只有 $$$1$$$ 个起点符合条件 。

在第二组测试数据中 ， 起始点为 $$$0$$$ 和 $$$12$$$ 时 ， 均能解码出连续的 $$$1, 2, 0$$$ ， 因此共有 $$$2$$$ 个合法的起始点 。