6479：质数串

题目描述

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

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

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

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

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

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

输入解释

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

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

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

输出解释

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

输入样例

输出样例

12
11
2

来自杭电HDUOJ的附加信息

Author	Claris
Recommend	liuyiding

该题目是Virtual Judge题目，来自杭电HDUOJ

题目来源 Championship

源链接： HDU-6479

最后修改于 2020-10-25T23:31:43+00:00 由爬虫自动更新

共提交 0 次

通过率 --%

时间上限	内存上限
2000/1000MS(Java/Others)	65535/102400K(Java/Others)