#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;

const int maxn = 200, maxm = 1e7;
int n, m, k, p[maxm / 10 + 3], a[maxn + 3], mat[maxn + 3];
map<int, bool> M;
bool b[maxm + 3], vis[maxn + 3];
vector<int> G[maxn + 3];

void prework(int n) {
	for (int i = 2; i <= n; i++) {
		if (!b[i]) p[++k] = i;
		for (int j = 1; j <= k && i * p[j] <= n; j++) {
			b[i * p[j]] = true;
			if (i % p[j] == 0) break;
		}
	}
	b[1] = b[2] = true;
}

bool dfs(int u) {
	for (int i = 0, v; i < G[u].size(); i++) {
		if (!vis[v = G[u][i]]) {
			vis[v] = true;
			if (!mat[v] || dfs(mat[v])) {
				mat[v] = u, mat[u] = v;
				return true;
			}
		}
	}
	return false;
}

int main() {
	prework(maxm);
	scanf("%d", &n);
	for (int i = 1, x; i <= n; i++) {
		scanf("%d", &x);
		M[x] ^= 1, M[x + 1] ^= 1;
	}
	for (map<int, bool>::iterator it = M.begin(); it != M.end(); it++) {
		if (it -> se) a[++m] = it -> fi;
	}
	for (int i = 1; i <= m; i++) {
		for (int j = i + 1; j <= m; j++) {
			if (!b[a[j] - a[i]]) {
				G[i].push_back(j), G[j].push_back(i);
			}
		}
	}
	int ans = 0;
	for (int i = 1; i <= m; i++) if (a[i] % 2 && !mat[i]) {
		fill(vis + 1, vis + m + 1, false), ans += dfs(i);
	}
	int odd = 0, even = 0;
	for (int i = 1; i <= m; i++) if (!mat[i]) {
		if (a[i] % 2) {
			if (odd) odd = 0, ans += 2;
			else odd = 1;
		} else {
			if (even) even = 0, ans += 2;
			else even = 1;
		}
	}
	if (odd && even) ans += 3;
	printf("%d\n", ans);
	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 fi first
#define se second
using namespace std;

const int maxn = 200, maxm = 1e7;
int n, m, k, p[maxm / 10 + 3], a[maxn + 3], mat[maxn + 3];
map<int, bool> M;
bool b[maxm + 3], vis[maxn + 3];
vector<int> G[maxn + 3];

void prework(int n) {
	for (int i = 2; i <= n; i++) {
		if (!b[i]) p[++k] = i;
		for (int j = 1; j <= k && i * p[j] <= n; j++) {
			b[i * p[j]] = true;
			if (i % p[j] == 0) break;
		}
	}
	b[1] = b[2] = true;
}

bool dfs(int u) {
	for (int i = 0, v; i < G[u].size(); i++) {
		if (!vis[v = G[u][i]]) {
			vis[v] = true;
			if (!mat[v] || dfs(mat[v])) {
				mat[v] = u, mat[u] = v;
				return true;
			}
		}
	}
	return false;
}

int main() {
	prework(maxm);
	scanf("%d", &n);
	for (int i = 1, x; i <= n; i++) {
		scanf("%d", &x);
		M[x] ^= 1, M[x + 1] ^= 1;
	}
	for (map<int, bool>::iterator it = M.begin(); it != M.end(); it++) {
		if (it -> se) a[++m] = it -> fi;
	}
	for (int i = 1; i <= m; i++) {
		for (int j = i + 1; j <= m; j++) {
			if (!b[a[j] - a[i]]) {
				G[i].push_back(j), G[j].push_back(i);
			}
		}
	}
	int ans = 0;
	for (int i = 1; i <= m; i++) if (a[i] % 2 && !mat[i]) {
		fill(vis + 1, vis + m + 1, false), ans += dfs(i);
	}
	int odd = 0, even = 0;
	for (int i = 1; i <= m; i++) if (!mat[i]) {
		if (a[i] % 2) {
			if (odd) odd = 0, ans += 2;
			else odd = 1;
		} else {
			if (even) even = 0, ans += 2;
			else even = 1;
		}
	}
	if (odd && even) ans += 3;
	printf("%d\n", ans);
	return 0;
}
```