Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

A. 好数据包
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

小明在研究二进制信号传输系统。在接收到一串由字符 $$$\mathtt{0}$$$ 和 $$$\mathtt{1}$$$ 组成的长度为 $$$n$$$ 的信号 $$$S$$$（下标从 $$$1$$$ 到 $$$n$$$）后，他需要将这段信号完整地分割成若干数据包，每个数据包都是 $$$S$$$ 的一段非空连续子串。

如果一个数据包中字符 $$$\mathtt{1}$$$ 的出现次数是一个质数$$$^{\text{∗}}$$$，则称该数据包是一个「好数据包」。

小明希望划分出的每个数据包都是「好数据包」。请你求出最多能划分出的数据包个数 $$$k$$$；如果不存在满足要求的划分，请输出 $$$-1$$$。

$$$^{\text{∗}}$$$质数是只有两个不同的正因数的自然数。例如 $$$2$$$、$$$3$$$、$$$5$$$、$$$7$$$、$$$11$$$ 都是质数，而 $$$0$$$、$$$1$$$、$$$4$$$、$$$6$$$、$$$8$$$、$$$9$$$ 都不是质数。

Input

本题的输入包含多组测试用例。

第一行一个整数 $$$T$$$（$$$1 \leq T \leq 10^5$$$），表示测试用例的数量。对于每组测试用例：

  • 第一行一个整数 $$$n$$$（$$$1 \leq n \leq 10^5$$$），表示信号 $$$S$$$ 的长度；
  • 第二行一个长度为 $$$n$$$ 的字符串 $$$S$$$，仅包含字符 $$$\mathtt{0}$$$ 和 $$$\mathtt{1}$$$，表示接收到的信号。

保证所有测试用例的 $$$n$$$ 的总和不超过 $$$2 \times 10^5$$$。

Output

对于每组测试用例：输出一行，包含一个整数 $$$k$$$，表示最多能划分出的数据包个数；如果不存在满足要求的划分，则输出 $$$-1$$$。

Example
Input
4
6
101101
3
010
8
11111111
5
00000
Output
2
-1
4
-1
Note

对于第一组测试用例，$$$S = \mathtt{101101}$$$，共包含 $$$4$$$ 个 $$$\mathtt{1}$$$。一种最优的划分为 $$$\mathtt{101} \mid \mathtt{101}$$$，两个数据包各包含 $$$2$$$ 个 $$$\mathtt{1}$$$，而 $$$2$$$ 是质数，因此这两个数据包都是「好数据包」。可以证明，不存在划分为 $$$3$$$ 个或更多「好数据包」的方案，所以答案为 $$$2$$$。

对于第二组测试用例，$$$S = \mathtt{010}$$$，仅包含 $$$1$$$ 个 $$$\mathtt{1}$$$。由于 $$$1$$$ 不是质数，并且继续划分只能得到 $$$0$$$ 个 $$$\mathtt{1}$$$ 以及 $$$1$$$ 个 $$$\mathtt{1}$$$ 的数据包，因此不存在方案，输出 $$$-1$$$。

对于第三组测试用例，$$$S = \mathtt{11111111}$$$，共包含 $$$8$$$ 个 $$$\mathtt{1}$$$。一种最优的划分为 $$$\mathtt{11} \mid \mathtt{11} \mid \mathtt{11} \mid \mathtt{11}$$$，每个数据包各包含 $$$2$$$ 个 $$$\mathtt{1}$$$，可以证明不存在更优方案，所以答案为 $$$4$$$。