# include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn(2005);
const int mxsz(1e7);

int n, x[maxn], pr[mxsz / 10], tot, pos[maxn], vis[maxn];
int first[maxn], cnt, idx, match[maxn], num;
bitset <mxsz + 5> ispr;

struct Edge {
	int to, next;
} edge[maxn * maxn];

inline void Add(int u, int v) {
	edge[cnt] = (Edge){v, first[u]}, first[u] = cnt++;
}

int Dfs(int u) {
	int e, v;
	for (e = first[u]; ~e; e = edge[e].next)
		if (vis[v = edge[e].to] != idx) {
			vis[v] = idx;
			if (!match[v] || Dfs(match[v]))	return match[v] = u, 1;
		}
	return 0;
}

int main() {
	memset(first, -1, sizeof(first));
	int i, j, ans, cnt0, cnt1;
	scanf("%d", &n);
	for (i = 1; i <= n; ++i) scanf("%d", &x[i]);
	sort(x + 1, x + n + 1);
	for (i = 2; i <= x[n]; ++i) {
		if (!ispr[i]) pr[++tot] = i;
		for (j = 1; j <= tot && pr[j] * i <= x[n]; ++j) {
			ispr[pr[j] * i] = 1;
			if (!(i % pr[j])) break;
		}
	}
	ans = cnt0 = cnt1 = 0;
	for (i = j = 1; i <= n; i = j) {
		while (x[j] == x[i] + j - i) ++j;
		pos[++num] = x[i], pos[++num] = x[j - 1] + 1;
	}
	for (i = 1; i <= num; ++i)
		if (pos[i] & 1) ++cnt1;
		else ++cnt0;
	for (i = 1; i <= num; ++i)
		if (pos[i] & 1)
			for (j = 1; j <= num; ++j)
				if ((~pos[j] & 1) && abs(pos[j] - pos[i]) > 2 && !ispr[abs(pos[j] - pos[i])]) Add(i, j);
	for (i = 1; i <= num; ++i)
		if (pos[i] & 1) ++idx, ans += Dfs(i);
	cnt0 -= ans, cnt1 -= ans;
	ans += (cnt0 / 2) * 2 + (cnt1 / 2) * 2;
	if (cnt0 & 1) ans += 3;
	printf("%d\n", ans);
	return 0;
}
### Prompt

Please provide a cpp coded solution 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>
using namespace std;
typedef long long ll;

const int maxn(2005);
const int mxsz(1e7);

int n, x[maxn], pr[mxsz / 10], tot, pos[maxn], vis[maxn];
int first[maxn], cnt, idx, match[maxn], num;
bitset <mxsz + 5> ispr;

struct Edge {
	int to, next;
} edge[maxn * maxn];

inline void Add(int u, int v) {
	edge[cnt] = (Edge){v, first[u]}, first[u] = cnt++;
}

int Dfs(int u) {
	int e, v;
	for (e = first[u]; ~e; e = edge[e].next)
		if (vis[v = edge[e].to] != idx) {
			vis[v] = idx;
			if (!match[v] || Dfs(match[v]))	return match[v] = u, 1;
		}
	return 0;
}

int main() {
	memset(first, -1, sizeof(first));
	int i, j, ans, cnt0, cnt1;
	scanf("%d", &n);
	for (i = 1; i <= n; ++i) scanf("%d", &x[i]);
	sort(x + 1, x + n + 1);
	for (i = 2; i <= x[n]; ++i) {
		if (!ispr[i]) pr[++tot] = i;
		for (j = 1; j <= tot && pr[j] * i <= x[n]; ++j) {
			ispr[pr[j] * i] = 1;
			if (!(i % pr[j])) break;
		}
	}
	ans = cnt0 = cnt1 = 0;
	for (i = j = 1; i <= n; i = j) {
		while (x[j] == x[i] + j - i) ++j;
		pos[++num] = x[i], pos[++num] = x[j - 1] + 1;
	}
	for (i = 1; i <= num; ++i)
		if (pos[i] & 1) ++cnt1;
		else ++cnt0;
	for (i = 1; i <= num; ++i)
		if (pos[i] & 1)
			for (j = 1; j <= num; ++j)
				if ((~pos[j] & 1) && abs(pos[j] - pos[i]) > 2 && !ispr[abs(pos[j] - pos[i])]) Add(i, j);
	for (i = 1; i <= num; ++i)
		if (pos[i] & 1) ++idx, ans += Dfs(i);
	cnt0 -= ans, cnt1 -= ans;
	ans += (cnt0 / 2) * 2 + (cnt1 / 2) * 2;
	if (cnt0 & 1) ans += 3;
	printf("%d\n", ans);
	return 0;
}
```