#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;
struct Edge{
	int v,c,nxt;
}e[600010];int tot=1;
int first[210];
void build(int u,int v,int c)
{
	e[++tot]=(Edge){v,c,first[u]};
	first[u]=tot;
	return ;
}
void adde(int u,int v,int c)
{
	build(u,v,c);
	build(v,u,0);
	return ;
}
int S,T;
queue<int>q;
int dep[210];
bool bfs()
{
	memset(dep,0,sizeof(dep));
	dep[S]=1;q.push(S);
	while(!q.empty())
	{
		int u=q.front();q.pop();
		for(int i=first[u];i;i=e[i].nxt)
			if(e[i].c&&!dep[e[i].v])
			{
				dep[e[i].v]=dep[u]+1;
				q.push(e[i].v);
			}
	}
	return dep[T]>0;
}
int cur[210];
int dfs(int u,int flow)
{
	if(u==T)return flow;
	for(int &i=cur[u];i;i=e[i].nxt)
		if(e[i].c&&dep[u]+1==dep[e[i].v])
		{
			int d=dfs(e[i].v,min(flow,e[i].c));
			if(d){
				e[i].c-=d;
				e[i^1].c+=d;
				return d;
			}
		}
	return 0;
}
int dinic()
{
	int ans=0;
	while(bfs()){
		for(int i=S;i<=T;i++)
			cur[i]=first[i];
		int d;
		while(d=dfs(S,1e9))
			ans+=d;
	}
	return ans;
}
bool check(int a)
{
	if(a<=2)return false;
	for(int i=2;i*i<=a;i++)
		if(a%i==0)return false;
	return true;
}
int x[210];
int vis[10000010];
int main()
{
	int n;scanf("%d",&n);
	int N=0;
	int mx=0;
	for(int i=1;i<=n;i++)
	{
		int a;scanf("%d",&a);
		vis[a]=1;mx=max(mx,a);
	}
	for(int i=1;i<=mx+1;i++)
		if(vis[i]!=vis[i-1])
			x[++N]=i;
	S=0;T=N+1;
	int cntx=0,cnty=0;
	for(int i=1;i<=N;i++)
		if(x[i]&1){
			adde(S,i,1);
			cntx++;
		}
		else{
			adde(i,T,1);
			cnty++;
		}
	for(int i=1;i<=N;i++)
		if(x[i]&1){
			for(int j=1;j<=N;j++)
				if(check(abs(x[i]-x[j])))
					adde(i,j,1);
		}
	int res=dinic();
	int ans=res+(cntx-res)/2*2+(cnty-res)/2*2+((cntx-res)&1)*3;
	printf("%d\n",ans);
	return 0;
}
### Prompt

Generate 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<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;
struct Edge{
	int v,c,nxt;
}e[600010];int tot=1;
int first[210];
void build(int u,int v,int c)
{
	e[++tot]=(Edge){v,c,first[u]};
	first[u]=tot;
	return ;
}
void adde(int u,int v,int c)
{
	build(u,v,c);
	build(v,u,0);
	return ;
}
int S,T;
queue<int>q;
int dep[210];
bool bfs()
{
	memset(dep,0,sizeof(dep));
	dep[S]=1;q.push(S);
	while(!q.empty())
	{
		int u=q.front();q.pop();
		for(int i=first[u];i;i=e[i].nxt)
			if(e[i].c&&!dep[e[i].v])
			{
				dep[e[i].v]=dep[u]+1;
				q.push(e[i].v);
			}
	}
	return dep[T]>0;
}
int cur[210];
int dfs(int u,int flow)
{
	if(u==T)return flow;
	for(int &i=cur[u];i;i=e[i].nxt)
		if(e[i].c&&dep[u]+1==dep[e[i].v])
		{
			int d=dfs(e[i].v,min(flow,e[i].c));
			if(d){
				e[i].c-=d;
				e[i^1].c+=d;
				return d;
			}
		}
	return 0;
}
int dinic()
{
	int ans=0;
	while(bfs()){
		for(int i=S;i<=T;i++)
			cur[i]=first[i];
		int d;
		while(d=dfs(S,1e9))
			ans+=d;
	}
	return ans;
}
bool check(int a)
{
	if(a<=2)return false;
	for(int i=2;i*i<=a;i++)
		if(a%i==0)return false;
	return true;
}
int x[210];
int vis[10000010];
int main()
{
	int n;scanf("%d",&n);
	int N=0;
	int mx=0;
	for(int i=1;i<=n;i++)
	{
		int a;scanf("%d",&a);
		vis[a]=1;mx=max(mx,a);
	}
	for(int i=1;i<=mx+1;i++)
		if(vis[i]!=vis[i-1])
			x[++N]=i;
	S=0;T=N+1;
	int cntx=0,cnty=0;
	for(int i=1;i<=N;i++)
		if(x[i]&1){
			adde(S,i,1);
			cntx++;
		}
		else{
			adde(i,T,1);
			cnty++;
		}
	for(int i=1;i<=N;i++)
		if(x[i]&1){
			for(int j=1;j<=N;j++)
				if(check(abs(x[i]-x[j])))
					adde(i,j,1);
		}
	int res=dinic();
	int ans=res+(cntx-res)/2*2+(cnty-res)/2*2+((cntx-res)&1)*3;
	printf("%d\n",ans);
	return 0;
}
```