#include<bits/stdc++.h>
#define inf 1e9
using namespace std;
struct node{
	int nxt,to,weigh;
}edge[400010];
int head[100100],n,S,T,cnt=1,level[100100];
int a[10010],b[10010],c[10001000],sum,tot,ans;
queue<int> qu;
bool check(int a){
	if(a<=2)return false; 
	for(int i=2;i<=sqrt(a);i++)
		if(a%i==0)return false;
	return true;
}
void addedge(int x,int y,int z){
	edge[++cnt].nxt=head[x];
	edge[cnt].to=y;
	edge[cnt].weigh=z;
	head[x]=cnt;
	edge[++cnt].nxt=head[y];
	edge[cnt].to=x;
	edge[cnt].weigh=0;
	head[y]=cnt;	
}
bool bfs(){
	memset(level,-1,sizeof(level));
	level[S]=0;
	qu.push(S);
	while(!qu.empty()){
		int u=qu.front();
		qu.pop();
		for(int i=head[u];i;i=edge[i].nxt){
			int upup=edge[i].to;
			if(edge[i].weigh!=0 && level[upup]==-1){
				level[upup]=level[u]+1;
				qu.push(upup);
			}
		}
	}
	if(level[T]==-1)return false;
	return true;
}
int dfs(int x,int flow){
	if(x==T)return flow;
	int rest=0;
	for(int i=head[x];i;i=edge[i].nxt){
		int upup=edge[i].to;
		if(rest==flow)break;
		if(level[upup]==level[x]+1){
			int sum=dfs(upup,min(flow-rest,edge[i].weigh));
			rest+=sum,edge[i].weigh-=sum;edge[i^1].weigh+=sum;
		}
	} 
	return rest;
}
int Dinic(){
	int ans=0;
	while(bfs())
		ans+=dfs(S,inf);
	return ans;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		c[a[i]]=1;
	}
	for(int i=1;i<=10000000;i++)
		if(c[i]!=c[i-1])
			b[++sum]=i;
	S=0,T=sum+1;
	for(int i=1;i<=sum;i++)
		if(b[i]&1){
			tot++;
			addedge(S,i,1);
			for(int j=1;j<=sum;j++)
				if(!(b[j]&1)&&check(abs(b[j]-b[i])))
					addedge(i,j,1);
		}
		else addedge(i,T,1);
	ans=Dinic();
	printf("%d\n",sum-ans+(tot-ans)%2);
	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<bits/stdc++.h>
#define inf 1e9
using namespace std;
struct node{
	int nxt,to,weigh;
}edge[400010];
int head[100100],n,S,T,cnt=1,level[100100];
int a[10010],b[10010],c[10001000],sum,tot,ans;
queue<int> qu;
bool check(int a){
	if(a<=2)return false; 
	for(int i=2;i<=sqrt(a);i++)
		if(a%i==0)return false;
	return true;
}
void addedge(int x,int y,int z){
	edge[++cnt].nxt=head[x];
	edge[cnt].to=y;
	edge[cnt].weigh=z;
	head[x]=cnt;
	edge[++cnt].nxt=head[y];
	edge[cnt].to=x;
	edge[cnt].weigh=0;
	head[y]=cnt;	
}
bool bfs(){
	memset(level,-1,sizeof(level));
	level[S]=0;
	qu.push(S);
	while(!qu.empty()){
		int u=qu.front();
		qu.pop();
		for(int i=head[u];i;i=edge[i].nxt){
			int upup=edge[i].to;
			if(edge[i].weigh!=0 && level[upup]==-1){
				level[upup]=level[u]+1;
				qu.push(upup);
			}
		}
	}
	if(level[T]==-1)return false;
	return true;
}
int dfs(int x,int flow){
	if(x==T)return flow;
	int rest=0;
	for(int i=head[x];i;i=edge[i].nxt){
		int upup=edge[i].to;
		if(rest==flow)break;
		if(level[upup]==level[x]+1){
			int sum=dfs(upup,min(flow-rest,edge[i].weigh));
			rest+=sum,edge[i].weigh-=sum;edge[i^1].weigh+=sum;
		}
	} 
	return rest;
}
int Dinic(){
	int ans=0;
	while(bfs())
		ans+=dfs(S,inf);
	return ans;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		c[a[i]]=1;
	}
	for(int i=1;i<=10000000;i++)
		if(c[i]!=c[i-1])
			b[++sum]=i;
	S=0,T=sum+1;
	for(int i=1;i<=sum;i++)
		if(b[i]&1){
			tot++;
			addedge(S,i,1);
			for(int j=1;j<=sum;j++)
				if(!(b[j]&1)&&check(abs(b[j]-b[i])))
					addedge(i,j,1);
		}
		else addedge(i,T,1);
	ans=Dinic();
	printf("%d\n",sum-ans+(tot-ans)%2);
	return 0;
}
```