#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;

const int MaxN = 100;
const int MaxM = 10000000;
const int MaxNV = MaxN * 2;

int n;
bool f[MaxM + 2];

int nL, qL[MaxNV + 1];
int nR, qR[MaxNV + 1];

bool mat[MaxNV + 1][MaxNV + 1];

bool bookR[MaxNV + 1];
int mateR[MaxNV + 1];

int pri_n, pri[MaxM / 8];
bool book[MaxM + 2];

inline void init_sieve(int n = MaxM + 1)
{
	book[1] = true;
	for (int i = 2; i <= n; ++i)
	{
		if (!book[i])
			pri[pri_n++] = i;

		for (int j = 0; j < pri_n; ++j)
		{
			int p = pri[j], d = i * p;
			if (d > n)
				break;
			book[d] = true;

			if (i % p == 0)
				break;
		}
	}
}

bool match(const int &u)
{
	for (int v = 1; v <= nR; ++v)
		if (mat[u][v] && !bookR[v])
		{
			bookR[v] = true;
			if (!mateR[v] || match(mateR[v]))
			{
				mateR[v] = u;
				return true;
			}
		}
	return false;
}

int main()
{
	init_sieve();

	cin >> n;
	for (int i = 0, x; i < n; ++i)
	{
		cin >> x;
		f[x] = true;
	}

	nL = nR = 0;
	for (int i = 1; i <= MaxM + 1; ++i)
		if (f[i] != f[i - 1])
		{
			if (i & 1)
				qL[++nL] = i;
			else
				qR[++nR] = i;
		}

	for (int i = 1; i <= nL; ++i)
		for (int j = 1; j <= nR; ++j)
			if (!book[abs(qL[i] - qR[j])])
				mat[i][j] = true;

	int n_matches = 0;
	for (int u = 1; u <= nL; ++u)
	{
		for (int v = 1; v <= nR; ++v)
			bookR[v] = false;

		n_matches += match(u);
	}

	int res = n_matches;
	res += (nL - n_matches >> 1) << 1;
	res += (nR - n_matches >> 1) << 1;
	res += 3 * ((nL ^ n_matches) & 1);

	cout << res << endl;

	return 0;
}
### Prompt

Please formulate a cpp solution to the following problem:

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.

Examples

Input

2
4 5


Output

2


Input

9
1 2 3 4 5 6 7 8 9


Output

3


Input

2
1 10000000


Output

4

### Response

```cpp
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;

const int MaxN = 100;
const int MaxM = 10000000;
const int MaxNV = MaxN * 2;

int n;
bool f[MaxM + 2];

int nL, qL[MaxNV + 1];
int nR, qR[MaxNV + 1];

bool mat[MaxNV + 1][MaxNV + 1];

bool bookR[MaxNV + 1];
int mateR[MaxNV + 1];

int pri_n, pri[MaxM / 8];
bool book[MaxM + 2];

inline void init_sieve(int n = MaxM + 1)
{
	book[1] = true;
	for (int i = 2; i <= n; ++i)
	{
		if (!book[i])
			pri[pri_n++] = i;

		for (int j = 0; j < pri_n; ++j)
		{
			int p = pri[j], d = i * p;
			if (d > n)
				break;
			book[d] = true;

			if (i % p == 0)
				break;
		}
	}
}

bool match(const int &u)
{
	for (int v = 1; v <= nR; ++v)
		if (mat[u][v] && !bookR[v])
		{
			bookR[v] = true;
			if (!mateR[v] || match(mateR[v]))
			{
				mateR[v] = u;
				return true;
			}
		}
	return false;
}

int main()
{
	init_sieve();

	cin >> n;
	for (int i = 0, x; i < n; ++i)
	{
		cin >> x;
		f[x] = true;
	}

	nL = nR = 0;
	for (int i = 1; i <= MaxM + 1; ++i)
		if (f[i] != f[i - 1])
		{
			if (i & 1)
				qL[++nL] = i;
			else
				qR[++nR] = i;
		}

	for (int i = 1; i <= nL; ++i)
		for (int j = 1; j <= nR; ++j)
			if (!book[abs(qL[i] - qR[j])])
				mat[i][j] = true;

	int n_matches = 0;
	for (int u = 1; u <= nL; ++u)
	{
		for (int v = 1; v <= nR; ++v)
			bookR[v] = false;

		n_matches += match(u);
	}

	int res = n_matches;
	res += (nL - n_matches >> 1) << 1;
	res += (nR - n_matches >> 1) << 1;
	res += 3 * ((nL ^ n_matches) & 1);

	cout << res << endl;

	return 0;
}
```