#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<cstring>

using namespace std;
using vi = vector<int>;
vi X;
int n;
vector<vi> C;
int used[207];
int S;
bool isprime(int n) {
	if (n <= 2)return false;
	for (int i = 2; i*i <= n; i++) {
		if (n%i == 0)return false;
	}
	return true;
}
bool dfs(int v) {
	used[v] = true;
	if (v == S + 1) return true;
	for (int i = 0; i < S + 2; i++) {
		if (!used[i] && C[v][i] > 0) {
			if (dfs(i)) {
				C[v][i]--;
				C[i][v]++;
				return true;
			}
		}
	}
	return false;
}
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		if (!X.empty() && X.back() == x) {
			X.pop_back();
			X.push_back(x + 1);
		}
		else {
			X.push_back(x);
			X.push_back(x + 1);
		}
	}
	int E = 0;
	int O = 0;
	for (int x : X) {
		if (x % 2 == 0) {
			E++;
		}
		else {
			O++;
		}
	}
	S = X.size();
	C.resize(S+2,vi(S+2,0));
	for (int i = 0; i < S; i++) {
		if (X[i] % 2 == 0) {
			C[S][i] = 1;
		}
		else {
			C[i][S + 1] = 1;
		}
	}
	for (int i = 0; i < S; i++) {
		for (int j = i; j < S; j++) {
			if (isprime(abs(X[i] - X[j]))) {
				int a = i;
				int b = j;
				if (X[b] % 2 == 0)swap(a, b);
				C[a][b] = 1;
			}
		}
	}
	int ans = 0;
	while (dfs(S)) {
		memset(used, 0, sizeof(used));
		ans++;
	}
	if ((E - ans) % 2 == 0) {
		cout << ans + (E - ans + O - ans) << endl;
	}
	else {
		cout << ans + (E - ans - 1 + O - ans - 1) + 3 << endl;
	}
}
### 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<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<cstring>

using namespace std;
using vi = vector<int>;
vi X;
int n;
vector<vi> C;
int used[207];
int S;
bool isprime(int n) {
	if (n <= 2)return false;
	for (int i = 2; i*i <= n; i++) {
		if (n%i == 0)return false;
	}
	return true;
}
bool dfs(int v) {
	used[v] = true;
	if (v == S + 1) return true;
	for (int i = 0; i < S + 2; i++) {
		if (!used[i] && C[v][i] > 0) {
			if (dfs(i)) {
				C[v][i]--;
				C[i][v]++;
				return true;
			}
		}
	}
	return false;
}
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		if (!X.empty() && X.back() == x) {
			X.pop_back();
			X.push_back(x + 1);
		}
		else {
			X.push_back(x);
			X.push_back(x + 1);
		}
	}
	int E = 0;
	int O = 0;
	for (int x : X) {
		if (x % 2 == 0) {
			E++;
		}
		else {
			O++;
		}
	}
	S = X.size();
	C.resize(S+2,vi(S+2,0));
	for (int i = 0; i < S; i++) {
		if (X[i] % 2 == 0) {
			C[S][i] = 1;
		}
		else {
			C[i][S + 1] = 1;
		}
	}
	for (int i = 0; i < S; i++) {
		for (int j = i; j < S; j++) {
			if (isprime(abs(X[i] - X[j]))) {
				int a = i;
				int b = j;
				if (X[b] % 2 == 0)swap(a, b);
				C[a][b] = 1;
			}
		}
	}
	int ans = 0;
	while (dfs(S)) {
		memset(used, 0, sizeof(used));
		ans++;
	}
	if ((E - ans) % 2 == 0) {
		cout << ans + (E - ans + O - ans) << endl;
	}
	else {
		cout << ans + (E - ans - 1 + O - ans - 1) + 3 << endl;
	}
}
```