#include <bits/stdc++.h>     
#define ll long long
#define mk make_pair
#define y1 yyyy
using namespace std;

const int N = 5e4 + 5;
const int mod = 1e9 + 7;

int n, a[N], my[N], ans;
bool b[N * 200];
vector<int> V[2], G[N];

bool find(int x) {
	for (int i = 0; i < G[x].size(); i++) {
		int u = G[x][i];
		if (b[u]) continue; 
		b[u] = 1;
		if (my[u] == -1 || find(my[u])) {
			my[u] = x;
			return 1;
		} 
	}
	return 0;
}

bool check(int x) { 
	if (x <= 2) return 0;
	for (int i = 2; i * i <= x; i++) {
		if (x % i == 0) return 0;
	}  
	return 1;
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i], b[a[i]] = 1;
	for (int i = 1; i <= 10000001; i++) {
		if (b[i] != b[i - 1]) V[i & 1].push_back(i);
	}
	memset(my, -1, sizeof(my));
	for (int i = 0; i < V[0].size(); i++) {
		for (int j = 0; j < V[1].size(); j++) {
			if (check(abs(V[0][i] - V[1][j]))) 
				G[i].push_back(j);
		}
	}
	for (int i = 0; i < V[0].size(); i++) {
		for (int j = 0; j < V[1].size(); j++) b[j] = 0;
		if (find(i)) ans++;
	}
	cout << ans + (V[0].size() - ans) / 2 * 2 + (V[1].size() - ans) / 2 * 2 + (V[0].size() - ans) % 2 * 3;
}
### 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 ll long long
#define mk make_pair
#define y1 yyyy
using namespace std;

const int N = 5e4 + 5;
const int mod = 1e9 + 7;

int n, a[N], my[N], ans;
bool b[N * 200];
vector<int> V[2], G[N];

bool find(int x) {
	for (int i = 0; i < G[x].size(); i++) {
		int u = G[x][i];
		if (b[u]) continue; 
		b[u] = 1;
		if (my[u] == -1 || find(my[u])) {
			my[u] = x;
			return 1;
		} 
	}
	return 0;
}

bool check(int x) { 
	if (x <= 2) return 0;
	for (int i = 2; i * i <= x; i++) {
		if (x % i == 0) return 0;
	}  
	return 1;
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i], b[a[i]] = 1;
	for (int i = 1; i <= 10000001; i++) {
		if (b[i] != b[i - 1]) V[i & 1].push_back(i);
	}
	memset(my, -1, sizeof(my));
	for (int i = 0; i < V[0].size(); i++) {
		for (int j = 0; j < V[1].size(); j++) {
			if (check(abs(V[0][i] - V[1][j]))) 
				G[i].push_back(j);
		}
	}
	for (int i = 0; i < V[0].size(); i++) {
		for (int j = 0; j < V[1].size(); j++) b[j] = 0;
		if (find(i)) ans++;
	}
	cout << ans + (V[0].size() - ans) / 2 * 2 + (V[1].size() - ans) / 2 * 2 + (V[0].size() - ans) % 2 * 3;
}
```