#include<bits/stdc++.h>
typedef long long ll;
ll gi(){
	ll x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch))f^=ch=='-',ch=getchar();
	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
	return f?x:-x;
}
int n,A[101],B[101];
bool yes[10000010];
int pr[670010],P;
int fir[210],dep[210],head[210],dis[3000010],nxt[3000010],w[3000010],id=1,S,T;
void link(int a,int b,int c){
	nxt[++id]=fir[a],fir[a]=id,dis[id]=b,w[id]=c;
	nxt[++id]=fir[b],fir[b]=id,dis[id]=a,w[id]=0;
}
bool BFS(){
	static int que[210],hd,tl;
	hd=tl=0;que[tl++]=S;memset(dep,0,sizeof dep);
	dep[S]=1;
	while(hd^tl){
		int x=que[hd++];
		for(int i=fir[x];i;i=nxt[i])
			if(w[i]&&!dep[dis[i]])dep[dis[i]]=dep[x]+1,que[tl++]=dis[i];
	}
	return dep[T];
}
int Dinic(int x,int maxflow){
	if(x==T)return maxflow;
	int ret=0;
	for(int&i=head[x];i;i=nxt[i])
		if(dep[dis[i]]==dep[x]+1&&w[i]){
			int d=Dinic(dis[i],std::min(w[i],maxflow-ret));
			w[i]-=d,w[i^1]+=d;ret+=d;if(ret==maxflow)break;
		}
	return ret;
}
int main(){
	n=gi();
	for(int i=1;i<=n;++i)A[i]=gi();
	std::sort(A+1,A+n+1),n=std::unique(A+1,A+n+1)-A-1;
	A[0]=A[n+1]=-1;
	int m=0;
	for(int i=1;i<=n;++i){
		if(A[i]!=A[i-1]+1)B[++m]=A[i]-1;
		if(A[i]!=A[i+1]-1)B[++m]=A[i];
	}
	S=m+1,T=m+2;
	int odd=0,even=0;
	for(int i=1;i<=m;++i)if(B[i]&1)++odd,link(S,i,1);else++even,link(i,T,1);
	for(int i=2;i<=A[n];++i){
		if(!yes[i])pr[++P]=i;
		for(int j=1;j<=P&&i*pr[j]<=A[n];++j){
			yes[i*pr[j]]=1;
			if(i%pr[j]==0)break;
		}
	}
	yes[0]=yes[1]=yes[2]=1;
	for(int i=1;i<=m;++i)if(B[i]&1)
		for(int j=1;j<=m;++j)
			if(!yes[abs(B[j]-B[i])])
				link(i,j,1);
	int ans=0;while(BFS())memcpy(head,fir,sizeof fir),ans+=Dinic(S,1e9);
	printf("%d\n",ans+2*((odd-ans>>1)+(even-ans>>1))+3*(odd-ans&1));
	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>
typedef long long ll;
ll gi(){
	ll x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch))f^=ch=='-',ch=getchar();
	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
	return f?x:-x;
}
int n,A[101],B[101];
bool yes[10000010];
int pr[670010],P;
int fir[210],dep[210],head[210],dis[3000010],nxt[3000010],w[3000010],id=1,S,T;
void link(int a,int b,int c){
	nxt[++id]=fir[a],fir[a]=id,dis[id]=b,w[id]=c;
	nxt[++id]=fir[b],fir[b]=id,dis[id]=a,w[id]=0;
}
bool BFS(){
	static int que[210],hd,tl;
	hd=tl=0;que[tl++]=S;memset(dep,0,sizeof dep);
	dep[S]=1;
	while(hd^tl){
		int x=que[hd++];
		for(int i=fir[x];i;i=nxt[i])
			if(w[i]&&!dep[dis[i]])dep[dis[i]]=dep[x]+1,que[tl++]=dis[i];
	}
	return dep[T];
}
int Dinic(int x,int maxflow){
	if(x==T)return maxflow;
	int ret=0;
	for(int&i=head[x];i;i=nxt[i])
		if(dep[dis[i]]==dep[x]+1&&w[i]){
			int d=Dinic(dis[i],std::min(w[i],maxflow-ret));
			w[i]-=d,w[i^1]+=d;ret+=d;if(ret==maxflow)break;
		}
	return ret;
}
int main(){
	n=gi();
	for(int i=1;i<=n;++i)A[i]=gi();
	std::sort(A+1,A+n+1),n=std::unique(A+1,A+n+1)-A-1;
	A[0]=A[n+1]=-1;
	int m=0;
	for(int i=1;i<=n;++i){
		if(A[i]!=A[i-1]+1)B[++m]=A[i]-1;
		if(A[i]!=A[i+1]-1)B[++m]=A[i];
	}
	S=m+1,T=m+2;
	int odd=0,even=0;
	for(int i=1;i<=m;++i)if(B[i]&1)++odd,link(S,i,1);else++even,link(i,T,1);
	for(int i=2;i<=A[n];++i){
		if(!yes[i])pr[++P]=i;
		for(int j=1;j<=P&&i*pr[j]<=A[n];++j){
			yes[i*pr[j]]=1;
			if(i%pr[j]==0)break;
		}
	}
	yes[0]=yes[1]=yes[2]=1;
	for(int i=1;i<=m;++i)if(B[i]&1)
		for(int j=1;j<=m;++j)
			if(!yes[abs(B[j]-B[i])])
				link(i,j,1);
	int ans=0;while(BFS())memcpy(head,fir,sizeof fir),ans+=Dinic(S,1e9);
	printf("%d\n",ans+2*((odd-ans>>1)+(even-ans>>1))+3*(odd-ans&1));
	return 0;
}


```