問題文

プライム君は$N$枚のカードを使って、とあるゲームをします。
各カードに正整数が書かれており、$i(1\leq i \leq N)$ 番目に書かれている正整数は$A_i$です。
プライム君は以下の操作を$0～N$回行うことで、獲得できるスコアを最大化したいです。

まだ選んでいないカードの中から$1$つ選び、そのカードに書かれている数だけ階段をのぼる。
スタートからのぼった段数の総和を$x$とすると、
$x$が素数のとき、スコアを$1$増やす。　そうでないとき、スコアを$1$減らす。

カードに書かれている数はプライム君から見えています。
プライム君が最適に操作を行うことで得られるスコアの最大値を求めてください。

制約

• $1 \leq N \leq 8$
• $1 \leq A_i \leq 10^5$

入力

入力はすべて整数である。
$N$
$A_1$ $A_2$ $...$ $A_N$

出力

得られるスコアの最大値を出力してください。

サンプル

4
2 4 5 7

3

$1$回目の操作で$「2」$が書かれたカードを選びます。のぼった段数の総和は$2$になるので、スコアが$1$増えます。
$2$回目の操作で$「5」$が書かれたカードを選びます。のぼった段数の総和は$7$になるので、スコアが$1$増えます。
$3$回目の操作で$「4」$が書かれたカードを選びます。のぼった段数の総和は$11$になるので、スコアが$1$増えます。
操作は好きなタイミングで終了できます。操作を$3$回で終えることで最終的なスコアは$3$となり、これが最大です。

4
4 4 4 4

0

操作を$1$回も行わないほうが良い場合もあります。

3
1 1 1

1

6
4 6 4 6 12 9

4