配点 : $1200$ 点

問題文

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

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

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

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

制約

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

入力

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

$N$

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

出力

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

2
4 5

2

例えば、次の順に操作を行えばよいです。

• $p = 5$ を選び、カード $1$, $2$, $3$, $4$, $5$ をひっくり返す。
• $p = 3$ を選び、カード $1$, $2$, $3$ をひっくり返す。

9
1 2 3 4 5 6 7 8 9

3

例えば、次の順に操作を行えばよいです。

• $p = 3$ を選び、カード $1$, $2$, $3$ をひっくり返す。
• $p = 3$ を選び、カード $4$, $5$, $6$ をひっくり返す。
• $p = 3$ を選び、カード $7$, $8$, $9$ をひっくり返す。

2
1 10000000

4