Home

Contest: Task: Related: TaskC TaskE

Score : $1200$ points

Problem Statement

There are infinitely many cards, numbered $1$, $2$, $3$, $...$ Initially, Cards $x_1$, $x_2$, $...$, $x_N$ are face up, and the others are face down.

Snuke can perform the following operation repeatedly:

  • Select a prime $p$ greater than or equal to $3$. Then, select $p$ consecutive cards and flip all of them.

Snuke's objective is to have all the cards face down. Find the minimum number of operations required to achieve the objective.

Constraints

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

Input

Input is given from Standard Input in the following format:

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

Output

Print the minimum number of operations required to achieve the objective.

Sample Input 1

2
4 5

Sample Output 1

2

Below is one way to achieve the objective in two operations:

  • Select $p = 5$ and flip Cards $1$, $2$, $3$, $4$ and $5$.
  • Select $p = 3$ and flip Cards $1$, $2$ and $3$.

Sample Input 2

9
1 2 3 4 5 6 7 8 9

Sample Output 2

3

Below is one way to achieve the objective in three operations:

  • Select $p = 3$ and flip Cards $1$, $2$ and $3$.
  • Select $p = 3$ and flip Cards $4$, $5$ and $6$.
  • Select $p = 3$ and flip Cards $7$, $8$ and $9$.

Sample Input 3

2
1 10000000

Sample Output 3

4