#include<stdio.h>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>

using namespace std;
int n;
const int maxn = 1e7+5;//40M
const int S = 1e7+2;
int pri[maxn],cnt; bool mk[maxn];
int A[maxn];
void oula() {
	mk[1] = mk[0] = 1;
	for(int i=2;i<=S;i++) {
		if(!mk[i]) { pri[++cnt]=i; }
		for(int j=1;j<=cnt&&1ll*pri[j]*i<=S;j++) {
			int k = pri[j]*i;
			mk[k] = 1;
			if(i%pri[j]==0) break;
		}
	}
}
int la[405],en[405*405],owo,nt[405*405];
void adg(int x,int y) {
	en[++owo]=y; nt[owo]=la[x]; la[x]=owo;
}
int cc[2];
int yo[2][405];
int link[405],vis[405];
int hungary(int x) {
	for(int it=la[x];it;it=nt[it]) {
		int y = en[it];
		if(vis[y]) continue;
		vis[y] = 1;
		if((!link[y])||(hungary(link[y]))) {
			link[y] = x; return 1;
		}
	}
	return 0;
}
int main() {
	oula();
	scanf("%d",&n);
	for(int i=1;i<=n;i++) {
		int x; scanf("%d",&x); A[x] = 1;
	}
	for(int i=1;i<=S;i++) {
		int cf = A[i-1]^A[i];
		if(cf) {
			++cc[i&1];
			yo[i&1][ cc[i&1] ] = i;
		}
	}
	for(int i=1;i<=cc[0];i++) {
		for(int j=1;j<=cc[1];j++) {
			if(!mk[abs(yo[0][i]-yo[1][j])])
			adg(i,j);
		}
	}
	int ans = 0;
	for(int i=1;i<=cc[0];i++) {
		for(int j=1;j<=cc[1];j++) vis[j] = 0;
		ans += hungary(i);
	}
	cc[0]-=ans; cc[1]-=ans;
	ans += cc[0]/2*2 + cc[1]/2*2 + (cc[0]&1)*3;
	printf("%d",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<stdio.h>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>

using namespace std;
int n;
const int maxn = 1e7+5;//40M
const int S = 1e7+2;
int pri[maxn],cnt; bool mk[maxn];
int A[maxn];
void oula() {
	mk[1] = mk[0] = 1;
	for(int i=2;i<=S;i++) {
		if(!mk[i]) { pri[++cnt]=i; }
		for(int j=1;j<=cnt&&1ll*pri[j]*i<=S;j++) {
			int k = pri[j]*i;
			mk[k] = 1;
			if(i%pri[j]==0) break;
		}
	}
}
int la[405],en[405*405],owo,nt[405*405];
void adg(int x,int y) {
	en[++owo]=y; nt[owo]=la[x]; la[x]=owo;
}
int cc[2];
int yo[2][405];
int link[405],vis[405];
int hungary(int x) {
	for(int it=la[x];it;it=nt[it]) {
		int y = en[it];
		if(vis[y]) continue;
		vis[y] = 1;
		if((!link[y])||(hungary(link[y]))) {
			link[y] = x; return 1;
		}
	}
	return 0;
}
int main() {
	oula();
	scanf("%d",&n);
	for(int i=1;i<=n;i++) {
		int x; scanf("%d",&x); A[x] = 1;
	}
	for(int i=1;i<=S;i++) {
		int cf = A[i-1]^A[i];
		if(cf) {
			++cc[i&1];
			yo[i&1][ cc[i&1] ] = i;
		}
	}
	for(int i=1;i<=cc[0];i++) {
		for(int j=1;j<=cc[1];j++) {
			if(!mk[abs(yo[0][i]-yo[1][j])])
			adg(i,j);
		}
	}
	int ans = 0;
	for(int i=1;i<=cc[0];i++) {
		for(int j=1;j<=cc[1];j++) vis[j] = 0;
		ans += hungary(i);
	}
	cc[0]-=ans; cc[1]-=ans;
	ans += cc[0]/2*2 + cc[1]/2*2 + (cc[0]&1)*3;
	printf("%d",ans );
}
```