|
||||||||||
质数串Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65535/102400 K (Java/Others)Total Submission(s): 147 Accepted Submission(s): 84 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 对于每组数据输出一行一个整数,即是质数串的非空连续子串数量。 Sample Input
Sample Output
Author Claris Source | ||||||||||
|