#include<algorithm>
#include<cstring>
#include<cctype>
#include<cstdio>
#define rep(i,x,y) for(int i=x; i<=y; ++i)

using namespace std;
const int N=105,M=10000005,INF=1000000000;
int n,a[N],L[N],R[N],totl,totr;
bool vis[M];
int prm[M],ans;
int s,t,h[N<<1],cnt,cur[N<<1],g[N<<1],dis[N<<1];
struct edge{int v,f,n;} e[(N*N+N+N)*2];

int getint()
{
	char ch;
	while(!isdigit(ch=getchar()));
	int x=ch-48;
	while(isdigit(ch=getchar())) x=x*10+ch-48;
	return x;
}

void addedge(int u,int v)
{
	e[cnt]=(edge){v,1,h[u]},h[u]=cnt++;
	e[cnt]=(edge){u,0,h[v]},h[v]=cnt++;
}

int isap(int x,int rt)
{
	if(x==t) return rt;
	int sum=0;
	for(int i=cur[x]; i!=-1; i=e[i].n)
		if(e[i].f && dis[x]==dis[e[i].v]+1)
		{
			int f=isap(e[i].v,min(rt-sum,e[i].f));
			e[i].f-=f,e[i^1].f+=f,sum+=f;
			if(cur[x]=i,sum==rt || dis[s]>=t) return sum;
		}
	if(!(--g[dis[x]++])) dis[s]=t;
	++g[dis[x]],cur[x]=h[x];
	return sum;
}

int main()
{
	n=getint();
	rep(i,1,n) a[i]=getint();
	for(int i=1,j; i<=n; i=j+1)
	{
		for(j=i; j+1<=n && a[j]+1==a[j+1]; ++j);
		if(a[i]&1) ++totl,L[totl]=a[i];
		else ++totr,R[totr]=a[i];
		if((a[j]+1)&1) ++totl,L[totl]=a[j]+1;
		else ++totr,R[totr]=a[j]+1;
	}
	
	vis[1]=1;
	rep(i,2,a[n])
	{
		if(!vis[i]) prm[++*prm]=i;
		rep(j,1,*prm)
		{
			if(i*prm[j]>a[n]) break;
			vis[i*prm[j]]=1;
			if(i%prm[j]==0) break;
		}
	}

	s=totl+totr+1,t=s+1;
	memset(h,-1,sizeof(h));
	rep(i,1,totl) rep(j,1,totr) if(!vis[abs(L[i]-R[j])]) addedge(i,j+totl);
	rep(i,1,totl) addedge(s,i);
	rep(i,1,totr) addedge(i+totl,t);
	memcpy(cur,h,sizeof(h));
	for(g[0]=t; dis[s]<t; ans+=isap(s,INF));
	printf("%d\n",ans+(totl-ans>>1)*2+(totr-ans>>1)*2+((totl-ans)&1)*3);
	return 0;
}
### Prompt

In Cpp, your task is to solve 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<algorithm>
#include<cstring>
#include<cctype>
#include<cstdio>
#define rep(i,x,y) for(int i=x; i<=y; ++i)

using namespace std;
const int N=105,M=10000005,INF=1000000000;
int n,a[N],L[N],R[N],totl,totr;
bool vis[M];
int prm[M],ans;
int s,t,h[N<<1],cnt,cur[N<<1],g[N<<1],dis[N<<1];
struct edge{int v,f,n;} e[(N*N+N+N)*2];

int getint()
{
	char ch;
	while(!isdigit(ch=getchar()));
	int x=ch-48;
	while(isdigit(ch=getchar())) x=x*10+ch-48;
	return x;
}

void addedge(int u,int v)
{
	e[cnt]=(edge){v,1,h[u]},h[u]=cnt++;
	e[cnt]=(edge){u,0,h[v]},h[v]=cnt++;
}

int isap(int x,int rt)
{
	if(x==t) return rt;
	int sum=0;
	for(int i=cur[x]; i!=-1; i=e[i].n)
		if(e[i].f && dis[x]==dis[e[i].v]+1)
		{
			int f=isap(e[i].v,min(rt-sum,e[i].f));
			e[i].f-=f,e[i^1].f+=f,sum+=f;
			if(cur[x]=i,sum==rt || dis[s]>=t) return sum;
		}
	if(!(--g[dis[x]++])) dis[s]=t;
	++g[dis[x]],cur[x]=h[x];
	return sum;
}

int main()
{
	n=getint();
	rep(i,1,n) a[i]=getint();
	for(int i=1,j; i<=n; i=j+1)
	{
		for(j=i; j+1<=n && a[j]+1==a[j+1]; ++j);
		if(a[i]&1) ++totl,L[totl]=a[i];
		else ++totr,R[totr]=a[i];
		if((a[j]+1)&1) ++totl,L[totl]=a[j]+1;
		else ++totr,R[totr]=a[j]+1;
	}
	
	vis[1]=1;
	rep(i,2,a[n])
	{
		if(!vis[i]) prm[++*prm]=i;
		rep(j,1,*prm)
		{
			if(i*prm[j]>a[n]) break;
			vis[i*prm[j]]=1;
			if(i%prm[j]==0) break;
		}
	}

	s=totl+totr+1,t=s+1;
	memset(h,-1,sizeof(h));
	rep(i,1,totl) rep(j,1,totr) if(!vis[abs(L[i]-R[j])]) addedge(i,j+totl);
	rep(i,1,totl) addedge(s,i);
	rep(i,1,totr) addedge(i+totl,t);
	memcpy(cur,h,sizeof(h));
	for(g[0]=t; dis[s]<t; ans+=isap(s,INF));
	printf("%d\n",ans+(totl-ans>>1)*2+(totr-ans>>1)*2+((totl-ans)&1)*3);
	return 0;
}
```