#include <bits/stdc++.h>

#define pb push_back

using namespace std;

const int MX = 10000001;

int n , a, x[MX + 1], visId, match[300], vis[300];
bool b[MX + 1], np[MX + 1];
vector<int> me, mo, g[300];

bool dfs(int u) {
	vis[u] = visId;
	for (int i = 0 ; i < g[u].size(); ++i) {
		int v = g[u][i];
		if (match[v] == -1 || vis[match[v]] != visId && dfs(match[v])) {
			match[v] = u;
			return true;
		}
	}
	return false;

}
int main() {
	for (int i = 2; i <= MX; ++i) {
		if (np[i])continue;
		for (int j = i + i; j <= MX ; j+=i){
			np[j] = 1;
		}
	}
	np[0] = np[1] = np[2] = 1;
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
		scanf("%d", &a);
		x[a] = 1;
	}
	for (int i = 1; i <= MX ; ++i) {
		b[i] = x[i] != x[i - 1];
		if (b[i] && (i % 2 == 0))me.pb(i);
		if (b[i] && (i % 2 == 1))mo.pb(i);
	}
	for (int i = 0; i < me.size(); ++i) {
		for (int j = 0 ; j < mo.size(); ++j) {
			if (!np[abs(me[i] - mo[j])]) {
				g[i].pb(j);
			}
		}
	}
	assert((me.size()+mo.size())%2 == 0);
	int res = 0;
	memset(match,-1,sizeof match);
	for (int i = 0; i < me.size(); ++i) {
		visId++;
		if (dfs(i))res++;
	}
	int even = me.size() - res;
	int odd = mo.size() - res;
	int ans = res + (even / 2) * 2 + (odd / 2) * 2 + (odd%2)*3;
	cout << ans << endl;
	return 0;
}
### Prompt

Create a solution in cpp for 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>

#define pb push_back

using namespace std;

const int MX = 10000001;

int n , a, x[MX + 1], visId, match[300], vis[300];
bool b[MX + 1], np[MX + 1];
vector<int> me, mo, g[300];

bool dfs(int u) {
	vis[u] = visId;
	for (int i = 0 ; i < g[u].size(); ++i) {
		int v = g[u][i];
		if (match[v] == -1 || vis[match[v]] != visId && dfs(match[v])) {
			match[v] = u;
			return true;
		}
	}
	return false;

}
int main() {
	for (int i = 2; i <= MX; ++i) {
		if (np[i])continue;
		for (int j = i + i; j <= MX ; j+=i){
			np[j] = 1;
		}
	}
	np[0] = np[1] = np[2] = 1;
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
		scanf("%d", &a);
		x[a] = 1;
	}
	for (int i = 1; i <= MX ; ++i) {
		b[i] = x[i] != x[i - 1];
		if (b[i] && (i % 2 == 0))me.pb(i);
		if (b[i] && (i % 2 == 1))mo.pb(i);
	}
	for (int i = 0; i < me.size(); ++i) {
		for (int j = 0 ; j < mo.size(); ++j) {
			if (!np[abs(me[i] - mo[j])]) {
				g[i].pb(j);
			}
		}
	}
	assert((me.size()+mo.size())%2 == 0);
	int res = 0;
	memset(match,-1,sizeof match);
	for (int i = 0; i < me.size(); ++i) {
		visId++;
		if (dfs(i))res++;
	}
	int even = me.size() - res;
	int odd = mo.size() - res;
	int ans = res + (even / 2) * 2 + (odd / 2) * 2 + (odd%2)*3;
	cout << ans << endl;
	return 0;
}
```