#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;

const int N=10005;
const int M=10000005;

int n1,n2,n,cnt,now,m,ans;
int lk[N],p1[N],p2[N],pri[M],p[N],c[M],b[M],tag[N];
bool vis[M];
vector<int> lev[N];

void getpri(int n){
	int i,j;
	for (i=2;i<=n;i++){
		if (!vis[i]) pri[++cnt]=i;
		for (j=1;j<=cnt&&pri[j]*i<=n;j++){
			vis[i*pri[j]]=1;
			if (i%pri[j]==0) break;
		}
	}
	vis[1]=vis[2]=1;
}

bool dfs(int k){
	int u,j;
	for (j=0;j<lev[k].size();j++){
		u=lev[k][j];
		if (tag[u]!=now){
			tag[u]=now;
			if (!lk[u]||dfs(lk[u])){
				lk[u]=k;
				return 1;
			}
		}
	}
	return 0;
}

int main(){
	int i,j;
	getpri(M-1);
	scanf("%d",&n);
	for (i=1;i<=n;i++) scanf("%d",&p[i]);
	sort(p+1,p+1+n); m=p[n]+1;
	for (i=1;i<=n;i++) b[p[i]]^=1;
	for (i=1;i<=m;i++) c[i]=b[i]!=b[i-1];
	for (i=1;i<=m;i++)
		if (c[i]){
			if (i&1) p1[++n1]=i;
			else p2[++n2]=i;
		}
	for (i=1;i<=n1;i++)
		for (j=1;j<=n2;j++)
			if (!vis[abs(p1[i]-p2[j])]) lev[i].push_back(j);
	for (i=1;i<=n1;i++){
		now++;
		ans+=dfs(i);
	}
	printf("%d\n",ans+(n1-ans)/2*2+(n2-ans)/2*2+(n1-ans)%2*3);
	return 0;
}
### Prompt

Please provide a Cpp coded solution 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<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;

const int N=10005;
const int M=10000005;

int n1,n2,n,cnt,now,m,ans;
int lk[N],p1[N],p2[N],pri[M],p[N],c[M],b[M],tag[N];
bool vis[M];
vector<int> lev[N];

void getpri(int n){
	int i,j;
	for (i=2;i<=n;i++){
		if (!vis[i]) pri[++cnt]=i;
		for (j=1;j<=cnt&&pri[j]*i<=n;j++){
			vis[i*pri[j]]=1;
			if (i%pri[j]==0) break;
		}
	}
	vis[1]=vis[2]=1;
}

bool dfs(int k){
	int u,j;
	for (j=0;j<lev[k].size();j++){
		u=lev[k][j];
		if (tag[u]!=now){
			tag[u]=now;
			if (!lk[u]||dfs(lk[u])){
				lk[u]=k;
				return 1;
			}
		}
	}
	return 0;
}

int main(){
	int i,j;
	getpri(M-1);
	scanf("%d",&n);
	for (i=1;i<=n;i++) scanf("%d",&p[i]);
	sort(p+1,p+1+n); m=p[n]+1;
	for (i=1;i<=n;i++) b[p[i]]^=1;
	for (i=1;i<=m;i++) c[i]=b[i]!=b[i-1];
	for (i=1;i<=m;i++)
		if (c[i]){
			if (i&1) p1[++n1]=i;
			else p2[++n2]=i;
		}
	for (i=1;i<=n1;i++)
		for (j=1;j<=n2;j++)
			if (!vis[abs(p1[i]-p2[j])]) lev[i].push_back(j);
	for (i=1;i<=n1;i++){
		now++;
		ans+=dfs(i);
	}
	printf("%d\n",ans+(n1-ans)/2*2+(n2-ans)/2*2+(n1-ans)%2*3);
	return 0;
}
```