#include<cstdio>
int n,x[210];
struct edge{int to,cap;edge*rev,*next;}E[40010],*ne=E,*fir[210],*cur[210];
void link(int a,int b,int c){
	*ne=(edge){b,c,ne+1,fir[a]};fir[a]=ne++;
	*ne=(edge){a,0,ne-1,fir[b]};fir[b]=ne++;
}
int Q[210],D[210];
int dfs(int i,int c){
	if(i==1||!c)return c;
	int fl=0,f;
	for(edge*&e=cur[i];e&&c;e=e->next)
		if(e->cap&&D[e->to]==D[i]-1&&(f=dfs(e->to,c<e->cap?c:e->cap)))
			fl+=f,e->cap-=f,e->rev->cap+=f,c-=f;
	return fl;
}
int mf(){
	for(int f=0;;f+=dfs(0,1<<30)){
		for(int i=0;i<=n+1;i++)D[i]=0,cur[i]=fir[i];
		for(int*h=Q,*t=Q+(D[*Q=1]=1);h<t;h++)
			for(edge*e=fir[*h];e;e=e->next)
				if(e->rev->cap&&!D[e->to])D[*t++=e->to]=D[*h]+1;
		if(!*D)return f;
	}
}
int pr[10000010],pc;
bool com[10000010];
int dif(int x,int y){return x>y?x-y:y-x;}
int main(){
	int N;scanf("%d",&N);
	while(N--){
		int v;scanf("%d",&v);
		if(n&&x[n-1]+1==v)++x[n-1];
		else x[n++]=v-1,x[n++]=v;
	}
	com[1]=1;
	for(int i=2;i<=x[n-1];i++){
		if(!com[i])pr[pc++]=i;
		for(int j=0;j<pc&&i*pr[j]<=x[n-1];j++){
			com[i*pr[j]]=1;
			if(i%pr[j]==0)break;
		}
	}
	int lc=0,rc=0;
	for(int i=0;i<n;i++){
		if(x[i]&1)link(i+2,1,1),rc++;
		else{
			link(0,i+2,1),lc++;
			for(int j=0;j<n;j++)if((x[j]&1)&&!com[dif(x[i],x[j])])link(i+2,j+2,1);
		}
	}
	int s=mf();
	lc-=s;rc-=s;
	printf("%d\n",s+lc/2*2+rc/2*2+lc%2*3);
}
### 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<cstdio>
int n,x[210];
struct edge{int to,cap;edge*rev,*next;}E[40010],*ne=E,*fir[210],*cur[210];
void link(int a,int b,int c){
	*ne=(edge){b,c,ne+1,fir[a]};fir[a]=ne++;
	*ne=(edge){a,0,ne-1,fir[b]};fir[b]=ne++;
}
int Q[210],D[210];
int dfs(int i,int c){
	if(i==1||!c)return c;
	int fl=0,f;
	for(edge*&e=cur[i];e&&c;e=e->next)
		if(e->cap&&D[e->to]==D[i]-1&&(f=dfs(e->to,c<e->cap?c:e->cap)))
			fl+=f,e->cap-=f,e->rev->cap+=f,c-=f;
	return fl;
}
int mf(){
	for(int f=0;;f+=dfs(0,1<<30)){
		for(int i=0;i<=n+1;i++)D[i]=0,cur[i]=fir[i];
		for(int*h=Q,*t=Q+(D[*Q=1]=1);h<t;h++)
			for(edge*e=fir[*h];e;e=e->next)
				if(e->rev->cap&&!D[e->to])D[*t++=e->to]=D[*h]+1;
		if(!*D)return f;
	}
}
int pr[10000010],pc;
bool com[10000010];
int dif(int x,int y){return x>y?x-y:y-x;}
int main(){
	int N;scanf("%d",&N);
	while(N--){
		int v;scanf("%d",&v);
		if(n&&x[n-1]+1==v)++x[n-1];
		else x[n++]=v-1,x[n++]=v;
	}
	com[1]=1;
	for(int i=2;i<=x[n-1];i++){
		if(!com[i])pr[pc++]=i;
		for(int j=0;j<pc&&i*pr[j]<=x[n-1];j++){
			com[i*pr[j]]=1;
			if(i%pr[j]==0)break;
		}
	}
	int lc=0,rc=0;
	for(int i=0;i<n;i++){
		if(x[i]&1)link(i+2,1,1),rc++;
		else{
			link(0,i+2,1),lc++;
			for(int j=0;j<n;j++)if((x[j]&1)&&!com[dif(x[i],x[j])])link(i+2,j+2,1);
		}
	}
	int s=mf();
	lc-=s;rc-=s;
	printf("%d\n",s+lc/2*2+rc/2*2+lc%2*3);
}
```