#XMOJ12793. 素数部分列

素数部分列

说明

时间限制:1 Sec 内存限制:256 MB 输入文件:prime.in 输出文件:prime.out

有一个由字符 1、3、5、7、9 构成的长度为 $N$ 的字符串 $S$。

你可以重复执行下面的操作,希望最大化操作次数:

- 选出 $S$ 的一个部分列(不需要连续),把这个部分列视作一个整数,若该整数是素数,则删除这个部分列。

求最多可以进行多少次操作。

输入格式

第一行一个整数 $N$。

第二行一个字符串 $S$。

输出格式

输出一行一个整数,表示答案。

样例

样例 1

6
993711

3

样例说明:

一种可行操作如下:

$9\underline{9}3\underline{7}11 \rightarrow 9\underline{3}11 \rightarrow 9\underline{11} \rightarrow 9$

下划线为每次选中的部分列。

$97,3,11$ 都是素数。

样例 2

5
99999

0

样例说明:

不存在可以作为素数的部分列,一次操作都无法执行。

样例 3

4
1333

3

数据范围

对于 20% 的数据,$N \le 50$。

对于 100% 的数据,$1 \le N \le 2\times 10^5$,$S$ 仅由 1、3、5、7、9 组成。