题目描述

無限枚のカードがあります。 カードには $1$, $2$, $3$, $...$ と番号が振られています。 最初、カード $x_1$, $x_2$, $...$, $x_N$ は表向きで、それら以外のカードは裏向きです。

すぬけ君は次の操作を繰り返し行うことができます。

• $3$ 以上の素数 $p$ を選ぶ。 番号が連続する $p$ 枚のカードを選び、それらすべてをひっくり返す。

すぬけ君の目標は、すべてのカードを裏向きにすることです。 すぬけ君が目標を達成するために必要な操作回数の最小値を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $x_1$ $x_2$ $...$ $x_N$

输出格式

すぬけ君が目標を達成するために必要な操作回数の最小値を出力せよ。

题目大意

有无限枚硬币，其中有$N$枚硬币$x_{1\ldots N}$初始时正面朝上，其余均为背面朝上，每次可以选择一段区间$[l,r]$，将区间内所有硬币翻转，其中$r-l+1$为一个奇数质数；问最少多少次能将所有硬币全部翻为背面朝上。

2
4 5

2

9
1 2 3 4 5 6 7 8 9

3

2
1 10000000

4

提示

制約

• $1\ <\ =\ N\ <\ =\ 100$
• $1\ <\ =\ x_1\ <\ x_2\ <\ ...\ <\ x_N\ <\ =\ 10^7$

Sample Explanation 1

例えば、次の順に操作を行えばよいです。 - $p\ =\ 5$ を選び、カード $1$, $2$, $3$, $4$, $5$ をひっくり返す。 - $p\ =\ 3$ を選び、カード $1$, $2$, $3$ をひっくり返す。

Sample Explanation 2

例えば、次の順に操作を行えばよいです。 - $p\ =\ 3$ を選び、カード $1$, $2$, $3$ をひっくり返す。 - $p\ =\ 3$ を選び、カード $4$, $5$, $6$ をひっくり返す。 - $p\ =\ 3$ を選び、カード $7$, $8$, $9$ をひっくり返す。