#include<bits/stdc++.h>

using namespace std;

#define abs abs_
inline int abs(int x){return x<0?-x:x;} 
inline bool chk(int n){if(n<=2)return false;for(int d=2;d*d<=n;d++)if(n%d==0)return false;return true;}

const int N=233,M=23333,inf=1e9;

int S,T,h[N],nxt[M],to[M],flow[M],cnt=1,qu[N],ql,qr,d[N];
void addedge(int u,int v,int c){
	to[++cnt]=v,nxt[cnt]=h[u],h[u]=cnt,flow[cnt]=c;
	to[++cnt]=u,nxt[cnt]=h[v],h[v]=cnt,flow[cnt]=0;
}
bool bfs(){
	for(int i=S;i<=T;i++)d[i]=-1;
	d[S]=0,qu[ql=qr=1]=S;
	while(ql<=qr){
		int u=qu[ql++];
		for(int i=h[u],v;i;i=nxt[i])if(d[v=to[i]]==-1&&flow[i])d[v]=d[u]+1,qu[++qr]=v;
		if(d[T]!=-1)break;
	}
	return d[T]!=-1;
}
int dfs(int u,int mf){
	if(u==T)return mf;
	int r=0,p;
	for(int i=h[u],v;i;i=nxt[i])if(d[v=to[i]]==d[u]+1&&flow[i])
		p=dfs(v,min(mf,flow[i])),flow[i]-=p,flow[i^1]+=p,r+=p,mf-=p; 
	return r;
}
int dinic(){
	int r=0;
	while(bfs())r+=dfs(S,inf);
	return r;
}

int n,m1,m2,odd[N],even[N];
set<int> dat;

int main(){
	scanf("%d",&n);
	for(int i=1,x;i<=n;i++){
		scanf("%d",&x);
		if(dat.count(x))dat.erase(x);else dat.insert(x);
		x++;
		if(dat.count(x))dat.erase(x);else dat.insert(x);
	}
	for(int x:dat)if(x&1)odd[++m1]=x;else even[++m2]=x;
	T=m1+m2+1;
	for(int i=1;i<=m1;i++)addedge(S,i,1);
	for(int i=1;i<=m2;i++)addedge(i+m1,T,1);
	for(int i=1;i<=m1;i++)for(int j=1;j<=m2;j++)
		if(chk(abs(odd[i]-even[j])))addedge(i,j+m1,1);
	int mch=dinic(),ans=m1+m2-mch+((m1-mch)&1); 
	printf("%d\n",ans); 
	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<bits/stdc++.h>

using namespace std;

#define abs abs_
inline int abs(int x){return x<0?-x:x;} 
inline bool chk(int n){if(n<=2)return false;for(int d=2;d*d<=n;d++)if(n%d==0)return false;return true;}

const int N=233,M=23333,inf=1e9;

int S,T,h[N],nxt[M],to[M],flow[M],cnt=1,qu[N],ql,qr,d[N];
void addedge(int u,int v,int c){
	to[++cnt]=v,nxt[cnt]=h[u],h[u]=cnt,flow[cnt]=c;
	to[++cnt]=u,nxt[cnt]=h[v],h[v]=cnt,flow[cnt]=0;
}
bool bfs(){
	for(int i=S;i<=T;i++)d[i]=-1;
	d[S]=0,qu[ql=qr=1]=S;
	while(ql<=qr){
		int u=qu[ql++];
		for(int i=h[u],v;i;i=nxt[i])if(d[v=to[i]]==-1&&flow[i])d[v]=d[u]+1,qu[++qr]=v;
		if(d[T]!=-1)break;
	}
	return d[T]!=-1;
}
int dfs(int u,int mf){
	if(u==T)return mf;
	int r=0,p;
	for(int i=h[u],v;i;i=nxt[i])if(d[v=to[i]]==d[u]+1&&flow[i])
		p=dfs(v,min(mf,flow[i])),flow[i]-=p,flow[i^1]+=p,r+=p,mf-=p; 
	return r;
}
int dinic(){
	int r=0;
	while(bfs())r+=dfs(S,inf);
	return r;
}

int n,m1,m2,odd[N],even[N];
set<int> dat;

int main(){
	scanf("%d",&n);
	for(int i=1,x;i<=n;i++){
		scanf("%d",&x);
		if(dat.count(x))dat.erase(x);else dat.insert(x);
		x++;
		if(dat.count(x))dat.erase(x);else dat.insert(x);
	}
	for(int x:dat)if(x&1)odd[++m1]=x;else even[++m2]=x;
	T=m1+m2+1;
	for(int i=1;i<=m1;i++)addedge(S,i,1);
	for(int i=1;i<=m2;i++)addedge(i+m1,T,1);
	for(int i=1;i<=m1;i++)for(int j=1;j<=m2;j++)
		if(chk(abs(odd[i]-even[j])))addedge(i,j+m1,1);
	int mch=dinic(),ans=m1+m2-mch+((m1-mch)&1); 
	printf("%d\n",ans); 
	return 0;
}
```