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

const int N = 210;

int n, x[N];
vector<int> dif;
int ans;
// for bipartite matching
vector<int> ver[2];
vector<int> g[N];
bool check[N];
int mx[N], my[N];

bool isprime(int x) {
	for (int i = 2; i * i <= x; ++i) if (x % i == 0) return false;
	return true;
}

bool dfs(int u) {
	if (!u) return true;
	for (int v : g[u]) if (!check[v]) {
		check[v] = 1;
		if (dfs(my[v])) {
			mx[u] = v; my[v] = u; return true;
		}
	}
	return false;
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) scanf("%d", x + i);
	for (int i = 1; i <= n; ++i) {
		if (!(i > 1 && x[i - 1] == x[i] - 1)) {
			dif.push_back(x[i]);
		}
		if (x[i + 1] != x[i] + 1) {
			dif.push_back(x[i] + 1);
		}
	}

	for (int i : dif) ver[i % 2].push_back(i);

	for (int i = 0; i < ver[0].size(); ++i) {
		for (int j = 0; j < ver[1].size(); ++j) {
			int dist = abs(ver[0][i] - ver[1][j]);
			if (dist <= 2) continue;
			if (isprime(dist)) {
				g[i + 1].push_back(j + 1);
			}
		}
	}

	// bipartite matching
	int sz = ver[0].size();
	int rem = sz, prev_rem = sz + 1;
	
	while(rem > 0 && rem < prev_rem) {
		prev_rem = rem;
		for (int i = 1; i <= sz; ++i) check[i] = false;
		for (int i = 1; i <= sz; ++i) if (!mx[i]) rem -= dfs(i);
	}

	for (int i = 1; i <= sz; ++i) if (mx[i]) ++ans;

	int v0 = ver[0].size() - ans;
	int v1 = ver[1].size() - ans;

	ans += 2 * (v0 / 2); v0 %= 2;
	ans += 2 * (v1 / 2); v1 %= 2;

	ans += (v0 == 1 && v1 == 1) * 3;

	printf("%d\n", ans);
}
### Prompt

Please create a solution in CPP 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 <bits/stdc++.h>
using namespace std;

const int N = 210;

int n, x[N];
vector<int> dif;
int ans;
// for bipartite matching
vector<int> ver[2];
vector<int> g[N];
bool check[N];
int mx[N], my[N];

bool isprime(int x) {
	for (int i = 2; i * i <= x; ++i) if (x % i == 0) return false;
	return true;
}

bool dfs(int u) {
	if (!u) return true;
	for (int v : g[u]) if (!check[v]) {
		check[v] = 1;
		if (dfs(my[v])) {
			mx[u] = v; my[v] = u; return true;
		}
	}
	return false;
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) scanf("%d", x + i);
	for (int i = 1; i <= n; ++i) {
		if (!(i > 1 && x[i - 1] == x[i] - 1)) {
			dif.push_back(x[i]);
		}
		if (x[i + 1] != x[i] + 1) {
			dif.push_back(x[i] + 1);
		}
	}

	for (int i : dif) ver[i % 2].push_back(i);

	for (int i = 0; i < ver[0].size(); ++i) {
		for (int j = 0; j < ver[1].size(); ++j) {
			int dist = abs(ver[0][i] - ver[1][j]);
			if (dist <= 2) continue;
			if (isprime(dist)) {
				g[i + 1].push_back(j + 1);
			}
		}
	}

	// bipartite matching
	int sz = ver[0].size();
	int rem = sz, prev_rem = sz + 1;
	
	while(rem > 0 && rem < prev_rem) {
		prev_rem = rem;
		for (int i = 1; i <= sz; ++i) check[i] = false;
		for (int i = 1; i <= sz; ++i) if (!mx[i]) rem -= dfs(i);
	}

	for (int i = 1; i <= sz; ++i) if (mx[i]) ++ans;

	int v0 = ver[0].size() - ans;
	int v1 = ver[1].size() - ans;

	ans += 2 * (v0 / 2); v0 %= 2;
	ans += 2 * (v1 / 2); v1 %= 2;

	ans += (v0 == 1 && v1 == 1) * 3;

	printf("%d\n", ans);
}
```