#include<bits/stdc++.h>
#define go(x, i) for(register int i = head[x]; i; i = nxt[i])
#define For(i, a, b) for(register int i = a; i <= b; ++ i)
#define SZ(x) int(x.size())

using namespace std;

const int maxn = 100 + 4, maxm = 1e7 + 10;
int P[maxn], C[maxn], n, vis[maxm];
int notprim[maxm], S[maxm];
vector<int> num, prime;

void Get_prime(int m)
{
	notprim[0] = notprim[1] = 1;
	For(i, 2, m)
	{
		if(!notprim[i])
			prime.push_back(i);
		int len = prime.size();
		For(j, 0, len - 1)
		{
			if(prime[j] * i > m)
				break;
			notprim[prime[j] * i] = 1;
			if(i % prime[j] == 0)
				break;
		}
	}
}

namespace Match
{
	const int N = 1e7 + 10;
	int to[N], head[N], nxt[N], e;
	int pre[N], vis[N], G[N], O[N], now, sum;
	void add(int x, int y)
	{
		to[++ e] = y;
		nxt[e] = head[x];
		head[x] = e;
	}
	bool dfs(int x)
	{
		go(x, i)
		{
			if(vis[to[i]] != now)
			{
				vis[to[i]] = now;
				if(!pre[to[i]] || dfs(pre[to[i]]))
				{
					pre[to[i]] = x;
					return 1;
				}
			}
		}
		return 0;
	}
	int match()
	{
		int res = 0;
		for(now = 1; now <= G[0]; ++ now)
			res += dfs(now);
		return res;
	}
	void solve()
	{
		int res = 0;
		For(i, 0, SZ(num) - 1)
			if(num[i] & 1)
				G[++ G[0]] = num[i];
			else
				O[++ O[0]] = num[i];
		For(i, 1, G[0])
			For(j, 1, O[0])
				if(!notprim[abs(G[i] - O[j])])
					add(i, j);
		res += match();
		memset(vis, 0, sizeof(vis));
		G[0] -= res, O[0] -= res;
		res += G[0] / 2 * 2, G[0] %= 2;
		res += O[0] / 2 * 2, O[0] %= 2;
		if(G[0] * O[0])
			res += 3;
		cout << res << endl;
	}
}

int main()
{
	Get_prime(1e7 + 5);
	scanf("%d", &n);
	For(i, 1, n)
		scanf("%d", &P[i]), vis[P[i]] ^= 1;
	For(i, 1, maxm - 1)
		if(vis[i] != vis[i - 1])
			num.push_back(i);
	memset(vis, 0, sizeof(vis));
	Match::solve();
	return 0;
}

### Prompt

Develop a solution in cpp to the problem described below:

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<bits/stdc++.h>
#define go(x, i) for(register int i = head[x]; i; i = nxt[i])
#define For(i, a, b) for(register int i = a; i <= b; ++ i)
#define SZ(x) int(x.size())

using namespace std;

const int maxn = 100 + 4, maxm = 1e7 + 10;
int P[maxn], C[maxn], n, vis[maxm];
int notprim[maxm], S[maxm];
vector<int> num, prime;

void Get_prime(int m)
{
	notprim[0] = notprim[1] = 1;
	For(i, 2, m)
	{
		if(!notprim[i])
			prime.push_back(i);
		int len = prime.size();
		For(j, 0, len - 1)
		{
			if(prime[j] * i > m)
				break;
			notprim[prime[j] * i] = 1;
			if(i % prime[j] == 0)
				break;
		}
	}
}

namespace Match
{
	const int N = 1e7 + 10;
	int to[N], head[N], nxt[N], e;
	int pre[N], vis[N], G[N], O[N], now, sum;
	void add(int x, int y)
	{
		to[++ e] = y;
		nxt[e] = head[x];
		head[x] = e;
	}
	bool dfs(int x)
	{
		go(x, i)
		{
			if(vis[to[i]] != now)
			{
				vis[to[i]] = now;
				if(!pre[to[i]] || dfs(pre[to[i]]))
				{
					pre[to[i]] = x;
					return 1;
				}
			}
		}
		return 0;
	}
	int match()
	{
		int res = 0;
		for(now = 1; now <= G[0]; ++ now)
			res += dfs(now);
		return res;
	}
	void solve()
	{
		int res = 0;
		For(i, 0, SZ(num) - 1)
			if(num[i] & 1)
				G[++ G[0]] = num[i];
			else
				O[++ O[0]] = num[i];
		For(i, 1, G[0])
			For(j, 1, O[0])
				if(!notprim[abs(G[i] - O[j])])
					add(i, j);
		res += match();
		memset(vis, 0, sizeof(vis));
		G[0] -= res, O[0] -= res;
		res += G[0] / 2 * 2, G[0] %= 2;
		res += O[0] / 2 * 2, O[0] %= 2;
		if(G[0] * O[0])
			res += 3;
		cout << res << endl;
	}
}

int main()
{
	Get_prime(1e7 + 5);
	scanf("%d", &n);
	For(i, 1, n)
		scanf("%d", &P[i]), vis[P[i]] ^= 1;
	For(i, 1, maxm - 1)
		if(vis[i] != vis[i - 1])
			num.push_back(i);
	memset(vis, 0, sizeof(vis));
	Match::solve();
	return 0;
}

```