#include <vector>
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = int(1E7) + 5;
const int MAXM = 100;

bool nprm[MAXN + 5];
int prm[MAXN + 5], pcnt;
void init() {
	nprm[1] = true;
	for(int i=2;i<=MAXN;i++) {
		if( !nprm[i] ) prm[++pcnt] = i;
		for(int j=1;prm[j]<=MAXN/i;j++) {
			nprm[i*prm[j]] = true;
			if( i % prm[j] == 0 ) break;
		}
	}
}

int a[MAXN + 5], b[2][MAXM + 5], cnt[2];

int G[MAXM + 5][MAXM + 5], lnk[MAXM + 5];
bool vis[MAXM + 5];
bool dfs(int x) {
	for(int i=1;i<=cnt[1];i++) {
		if( !vis[i] && G[x][i] ) {
			vis[i] = true;
			if( !lnk[i] || dfs(lnk[i]) ) {
				lnk[i] = x;
				return true;
			}
		}
	}
	return false;
}

int abs(int x) {return x >= 0 ? x : -x;}
int main() {
	init();
	int N; scanf("%d", &N);
	for(int i=1;i<=N;i++) {
		int x; scanf("%d", &x);
		a[x] = 1;
	}
	for(int i=1;i<=MAXN;i++)
		if( a[i] != a[i-1] ) b[i%2][++cnt[i%2]] = i;
	int ans = 0;
	for(int i=1;i<=cnt[0];i++)
		for(int j=1;j<=cnt[1];j++)
			G[i][j] = (!nprm[abs(b[0][i] - b[1][j])]);
	for(int i=1;i<=cnt[0];i++) {
		for(int j=1;j<=cnt[1];j++) vis[j] = false;
		if( dfs(i) ) ans++;
	}
	ans += (cnt[0] - ans)/2*2 + (cnt[1] - ans)/2*2;
	if( (cnt[0] - ans) & 1 ) ans += 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 <vector>
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = int(1E7) + 5;
const int MAXM = 100;

bool nprm[MAXN + 5];
int prm[MAXN + 5], pcnt;
void init() {
	nprm[1] = true;
	for(int i=2;i<=MAXN;i++) {
		if( !nprm[i] ) prm[++pcnt] = i;
		for(int j=1;prm[j]<=MAXN/i;j++) {
			nprm[i*prm[j]] = true;
			if( i % prm[j] == 0 ) break;
		}
	}
}

int a[MAXN + 5], b[2][MAXM + 5], cnt[2];

int G[MAXM + 5][MAXM + 5], lnk[MAXM + 5];
bool vis[MAXM + 5];
bool dfs(int x) {
	for(int i=1;i<=cnt[1];i++) {
		if( !vis[i] && G[x][i] ) {
			vis[i] = true;
			if( !lnk[i] || dfs(lnk[i]) ) {
				lnk[i] = x;
				return true;
			}
		}
	}
	return false;
}

int abs(int x) {return x >= 0 ? x : -x;}
int main() {
	init();
	int N; scanf("%d", &N);
	for(int i=1;i<=N;i++) {
		int x; scanf("%d", &x);
		a[x] = 1;
	}
	for(int i=1;i<=MAXN;i++)
		if( a[i] != a[i-1] ) b[i%2][++cnt[i%2]] = i;
	int ans = 0;
	for(int i=1;i<=cnt[0];i++)
		for(int j=1;j<=cnt[1];j++)
			G[i][j] = (!nprm[abs(b[0][i] - b[1][j])]);
	for(int i=1;i<=cnt[0];i++) {
		for(int j=1;j<=cnt[1];j++) vis[j] = false;
		if( dfs(i) ) ans++;
	}
	ans += (cnt[0] - ans)/2*2 + (cnt[1] - ans)/2*2;
	if( (cnt[0] - ans) & 1 ) ans += 3;
	printf("%d\n", ans);
}
```