#include<bits/stdc++.h>
using namespace std;
const int N=2e3+9,U=1e7+5;
int n,nn,XX[N],X[N],i,j,ls,flw;
struct edge{int to,next,f;}e[1<<21|1];
int h[N],cur[N],xb=1,S,T,d[N];
inline void addedge(int x,int y,int f){
	e[++xb]=(edge){y,h[x],f};h[x]=xb;
	e[++xb]=(edge){x,h[y],0};h[y]=xb;
}
inline bool bfs(){
	static int q[N],t,w;int u,i;
	q[t=0,w=1]=S;memset(d+1,0,T<<2);d[S]=1;
	for(;t<w;)for(i=h[u=q[++t]];i;i=e[i].next)if(e[i].f && !d[e[i].to])d[q[++w]=e[i].to]=d[u]+1;
	return d[T];
}
inline int dfs(int x,int f){
	if(x==T)return f;
	int ans=0,&i=cur[x],t;
	for(;i;i=e[i].next)if(d[e[i].to]==d[x]+1 && e[i].f && (t=dfs(e[i].to,min(f,e[i].f)))){
		e[i].f-=t;e[i^1].f+=t;ans+=t;f-=t;
		if(!f)break;
	}
	return ans;
}
bool b[U];
int main(){
	scanf("%d",&n);for(i=1;i<=n;++i)scanf("%d",XX+i);
	for(i=2;i<U;++i)if(!b[i])for(j=i*2;j<U;j+=i)b[j]=1;b[2]=b[1]=b[0]=1;
	sort(XX+1,XX+n+1);X[nn=1]=XX[1];if(n==1 || XX[1]+1<XX[2])X[++nn]=XX[1]+1;
	for(i=2;i<=n;++i){
		if(XX[i]>XX[i-1]+1)X[++nn]=XX[i];
		if(i==n || XX[i]+1<XX[i+1])X[++nn]=XX[i]+1;
	}
	S=nn+1;T=S+1;
	for(i=1;i<=nn;++i)if(X[i]&1){
		addedge(S,i,1);++ls;
		for(j=1;j<=nn;++j)if(!b[abs(X[i]-X[j])])addedge(i,j,1);
	}else addedge(i,T,1);
	for(;bfs();)memcpy(cur+1,h+1,T<<2),flw+=dfs(S,1<<25);
	printf("%d\n",nn-flw+(ls-flw)%2);
	return 0;
}
### Prompt

Create a solution in cpp for 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<bits/stdc++.h>
using namespace std;
const int N=2e3+9,U=1e7+5;
int n,nn,XX[N],X[N],i,j,ls,flw;
struct edge{int to,next,f;}e[1<<21|1];
int h[N],cur[N],xb=1,S,T,d[N];
inline void addedge(int x,int y,int f){
	e[++xb]=(edge){y,h[x],f};h[x]=xb;
	e[++xb]=(edge){x,h[y],0};h[y]=xb;
}
inline bool bfs(){
	static int q[N],t,w;int u,i;
	q[t=0,w=1]=S;memset(d+1,0,T<<2);d[S]=1;
	for(;t<w;)for(i=h[u=q[++t]];i;i=e[i].next)if(e[i].f && !d[e[i].to])d[q[++w]=e[i].to]=d[u]+1;
	return d[T];
}
inline int dfs(int x,int f){
	if(x==T)return f;
	int ans=0,&i=cur[x],t;
	for(;i;i=e[i].next)if(d[e[i].to]==d[x]+1 && e[i].f && (t=dfs(e[i].to,min(f,e[i].f)))){
		e[i].f-=t;e[i^1].f+=t;ans+=t;f-=t;
		if(!f)break;
	}
	return ans;
}
bool b[U];
int main(){
	scanf("%d",&n);for(i=1;i<=n;++i)scanf("%d",XX+i);
	for(i=2;i<U;++i)if(!b[i])for(j=i*2;j<U;j+=i)b[j]=1;b[2]=b[1]=b[0]=1;
	sort(XX+1,XX+n+1);X[nn=1]=XX[1];if(n==1 || XX[1]+1<XX[2])X[++nn]=XX[1]+1;
	for(i=2;i<=n;++i){
		if(XX[i]>XX[i-1]+1)X[++nn]=XX[i];
		if(i==n || XX[i]+1<XX[i+1])X[++nn]=XX[i]+1;
	}
	S=nn+1;T=S+1;
	for(i=1;i<=nn;++i)if(X[i]&1){
		addedge(S,i,1);++ls;
		for(j=1;j<=nn;++j)if(!b[abs(X[i]-X[j])])addedge(i,j,1);
	}else addedge(i,T,1);
	for(;bfs();)memcpy(cur+1,h+1,T<<2),flw+=dfs(S,1<<25);
	printf("%d\n",nn-flw+(ls-flw)%2);
	return 0;
}
```