#include<bits/stdc++.h>
#define ll long long
#define M 100010
using namespace std;
int n,A[10000010];
bool pri[10000010];
void init(int N){
	for(int i=2;i<=N;i++)
	if(!pri[i])
	for(int j=i+i;j<=N;j+=i)pri[j]=1;
	pri[1]=pri[2]=1;
}
int q1[3010],q2[3010],t1,t2,S,T;
int k,cnt,h,t;
int F[M],L[M],N[M],a[M],c[M],dis[M],q[M];
void add(int x,int y,int z){
	a[++k]=y;c[k]=z;
	N[k]=F[x];F[x]=k;
}
bool BFS(int x,int y){
	q[t=1]=x;h=0;
	for(int i=1;i<=n;i++)dis[i]=1000000000;
	dis[x]=0;
	while(h<t){
		x=q[++h];
		for(int i=F[x];i;i=N[i])if(c[i]&&dis[a[i]]>n){
			dis[a[i]]=dis[x]+1;
			if(a[i]==y)return 1;
			q[++t]=a[i];
		}
	}
	return dis[y]<=n;
}
int dfs(int x,int T,int flow){
	if(x==T)return flow;
	int used=0;
	for(int i=F[x];i;i=N[i])if(c[i]&&dis[a[i]]==dis[x]+1){
		const int v=dfs(a[i],T,min(flow-used,c[i]));
		if(!v)continue;c[i]-=v;c[i^1]+=v;used+=v;
		if(used>=flow)return used;
	}
	return used;
}
int dinic(int S,int T){
	int ans=0;
	while(BFS(S,T))ans+=dfs(S,T,1000000000);
	return ans;
}
int main(){
	scanf("%d",&n);init(10000000);k=1;
	for(int i=1;i<=n;i++){
		int x;
		scanf("%d",&x);
		A[x]^=1;
	}
	for(int i=1;i<=10000001;i++)if(A[i]!=A[i-1]){
		if(i&1)q1[++t1]=i;
		else q2[++t2]=i;
	}
	for(int i=1;i<=t1;i++)
	for(int j=1;j<=t2;j++)if(!pri[abs(q1[i]-q2[j])]){
		add(i,j+t1,1),add(j+t1,i,0);
	}
	
	S=t1+t2+1;T=n=t1+t2+2;
	for(int i=1;i<=t1;i++)add(S,i,1),add(i,S,0);
	for(int i=1;i<=t2;i++)add(i+t1,T,1),add(T,i+t1,0);
	int v=dinic(S,T);
	cout<<(t1-v)/2*2+(t2-v)/2*2+((t1-v)&1)*3+v;
	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>
#define ll long long
#define M 100010
using namespace std;
int n,A[10000010];
bool pri[10000010];
void init(int N){
	for(int i=2;i<=N;i++)
	if(!pri[i])
	for(int j=i+i;j<=N;j+=i)pri[j]=1;
	pri[1]=pri[2]=1;
}
int q1[3010],q2[3010],t1,t2,S,T;
int k,cnt,h,t;
int F[M],L[M],N[M],a[M],c[M],dis[M],q[M];
void add(int x,int y,int z){
	a[++k]=y;c[k]=z;
	N[k]=F[x];F[x]=k;
}
bool BFS(int x,int y){
	q[t=1]=x;h=0;
	for(int i=1;i<=n;i++)dis[i]=1000000000;
	dis[x]=0;
	while(h<t){
		x=q[++h];
		for(int i=F[x];i;i=N[i])if(c[i]&&dis[a[i]]>n){
			dis[a[i]]=dis[x]+1;
			if(a[i]==y)return 1;
			q[++t]=a[i];
		}
	}
	return dis[y]<=n;
}
int dfs(int x,int T,int flow){
	if(x==T)return flow;
	int used=0;
	for(int i=F[x];i;i=N[i])if(c[i]&&dis[a[i]]==dis[x]+1){
		const int v=dfs(a[i],T,min(flow-used,c[i]));
		if(!v)continue;c[i]-=v;c[i^1]+=v;used+=v;
		if(used>=flow)return used;
	}
	return used;
}
int dinic(int S,int T){
	int ans=0;
	while(BFS(S,T))ans+=dfs(S,T,1000000000);
	return ans;
}
int main(){
	scanf("%d",&n);init(10000000);k=1;
	for(int i=1;i<=n;i++){
		int x;
		scanf("%d",&x);
		A[x]^=1;
	}
	for(int i=1;i<=10000001;i++)if(A[i]!=A[i-1]){
		if(i&1)q1[++t1]=i;
		else q2[++t2]=i;
	}
	for(int i=1;i<=t1;i++)
	for(int j=1;j<=t2;j++)if(!pri[abs(q1[i]-q2[j])]){
		add(i,j+t1,1),add(j+t1,i,0);
	}
	
	S=t1+t2+1;T=n=t1+t2+2;
	for(int i=1;i<=t1;i++)add(S,i,1),add(i,S,0);
	for(int i=1;i<=t2;i++)add(i+t1,T,1),add(T,i+t1,0);
	int v=dinic(S,T);
	cout<<(t1-v)/2*2+(t2-v)/2*2+((t1-v)&1)*3+v;
	return 0;
}

```