#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
inline int read()
{
	int x;char c;
	while((c=getchar())<'0'||c>'9');
	for(x=c-'0';(c=getchar())>='0'&&c<='9';)x=x*10+c-'0';
	return x;
}
#define MX 10000001
int p[MX+5],pn,u[MX+5],v[MX+5],a[MX+5],an,b[MX+5],bn;
namespace MaxFlow
{
	const int MV=200,ME=10200,S=MV+1,T=MV+2,INF=0x7FFFFFFF;
	struct edge{int nx,t,w;}e[ME*2+5];
	int h[MV+5],en=1,d[MV+5],q[MV+5],qn,c[MV+5];
	inline void ins(int x,int y,int w)
	{
		e[++en]=(edge){h[x],y,w};h[x]=en;
		e[++en]=(edge){h[y],x,0};h[y]=en;
	}
	bool bfs()
	{
		int i,j;
		memset(d,0,sizeof(d));
		for(d[q[i=qn=0]=S]=1;i<=qn;++i)for(j=c[q[i]]=h[q[i]];j;j=e[j].nx)
			if(e[j].w&&!d[e[j].t])d[q[++qn]=e[j].t]=d[q[i]]+1;
		return d[T];
	}
	int dfs(int x,int r)
	{
		if(x==T)return r;
		int k,u=0;
		for(int&i=c[x];i;i=e[i].nx)if(e[i].w&&d[e[i].t]==d[x]+1)
		{
			k=dfs(e[i].t,r-u<e[i].w?r-u:e[i].w);
			u+=k;e[i].w-=k;e[i^1].w+=k;
			if(u==r)return r;
		}
		return d[x]=0,u;
	}
	int dinic(){int ans=0;while(bfs())ans+=dfs(S,INF);return ans;}
};
int main()
{
	int n,i,j,ans=0;
	for(u[1]=1,i=2;i<=MX;++i)
	{
		if(!u[i])p[++pn]=i;
		for(j=1;i*p[j]<=MX;++j){u[i*p[j]]=1;if(i%p[j]==0)break;}
	}
	for(n=read();n--;)v[i=read()]^=1,v[i+1]^=1;
	for(i=1;i<=MX;++i)if(v[i])i&1?a[++an]=i:b[++bn]=i;
	using namespace MaxFlow; 
	for(i=1;i<=an;++i)ins(S,i,1);
	for(j=1;j<=bn;++j)ins(an+j,T,1);
	for(i=1;i<=an;++i)for(j=1;j<=bn;++j)if(!u[abs(a[i]-b[j])])ins(i,an+j,1);
	ans=dinic();
	ans+=((an-ans)&1)+(an+bn-2*ans);
	printf("%d",ans);
}
### Prompt

Your task is to create a Cpp solution to 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<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
inline int read()
{
	int x;char c;
	while((c=getchar())<'0'||c>'9');
	for(x=c-'0';(c=getchar())>='0'&&c<='9';)x=x*10+c-'0';
	return x;
}
#define MX 10000001
int p[MX+5],pn,u[MX+5],v[MX+5],a[MX+5],an,b[MX+5],bn;
namespace MaxFlow
{
	const int MV=200,ME=10200,S=MV+1,T=MV+2,INF=0x7FFFFFFF;
	struct edge{int nx,t,w;}e[ME*2+5];
	int h[MV+5],en=1,d[MV+5],q[MV+5],qn,c[MV+5];
	inline void ins(int x,int y,int w)
	{
		e[++en]=(edge){h[x],y,w};h[x]=en;
		e[++en]=(edge){h[y],x,0};h[y]=en;
	}
	bool bfs()
	{
		int i,j;
		memset(d,0,sizeof(d));
		for(d[q[i=qn=0]=S]=1;i<=qn;++i)for(j=c[q[i]]=h[q[i]];j;j=e[j].nx)
			if(e[j].w&&!d[e[j].t])d[q[++qn]=e[j].t]=d[q[i]]+1;
		return d[T];
	}
	int dfs(int x,int r)
	{
		if(x==T)return r;
		int k,u=0;
		for(int&i=c[x];i;i=e[i].nx)if(e[i].w&&d[e[i].t]==d[x]+1)
		{
			k=dfs(e[i].t,r-u<e[i].w?r-u:e[i].w);
			u+=k;e[i].w-=k;e[i^1].w+=k;
			if(u==r)return r;
		}
		return d[x]=0,u;
	}
	int dinic(){int ans=0;while(bfs())ans+=dfs(S,INF);return ans;}
};
int main()
{
	int n,i,j,ans=0;
	for(u[1]=1,i=2;i<=MX;++i)
	{
		if(!u[i])p[++pn]=i;
		for(j=1;i*p[j]<=MX;++j){u[i*p[j]]=1;if(i%p[j]==0)break;}
	}
	for(n=read();n--;)v[i=read()]^=1,v[i+1]^=1;
	for(i=1;i<=MX;++i)if(v[i])i&1?a[++an]=i:b[++bn]=i;
	using namespace MaxFlow; 
	for(i=1;i<=an;++i)ins(S,i,1);
	for(j=1;j<=bn;++j)ins(an+j,T,1);
	for(i=1;i<=an;++i)for(j=1;j<=bn;++j)if(!u[abs(a[i]-b[j])])ins(i,an+j,1);
	ans=dinic();
	ans+=((an-ans)&1)+(an+bn-2*ans);
	printf("%d",ans);
}
```