Problem Description

一个正整数$x$是质数，当且仅当$x\geq 2$且$x$不是任何一个$[2,x-1]$的数的倍数。

一个数字串是''质数串''，当且仅当它的每个非空连续子串表示的数字都是质数。

例子1："373"是质数串，它的子串有"3"、"37"、"373"、"7"、"73"、"3"，这些串表示的数字都是质数。

例子2："55"不是质数串，因为"55"这个子串表示的数字不是质数。

相信聪明的你一定已经发现了一个事实，那就是质数串的限制很紧，所以质数串的数量其实非常稀少。

给定一个长度为$n$的数字串$S$，请统计它有多少个非空连续子串是质数串。注意两个子串如果位置不同也算不同，比如"373373"中，"373"要算入答案两次。

Input

第一行包含一个正整数$T(1\leq T\leq 30)$，表示测试数据的组数。

每组数据第一行包含一个正整数$n(1\leq n\leq 100000)$，表示数字串的长度。

第二行包含一个长度为$n$的仅由字符'1'到'9'组成的字符串$S$。

Output

对于每组数据输出一行一个整数，即是质数串的非空连续子串数量。

3
6
373373
5
37373
3
313

12
11
2

Author

Claris