#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=220,M=10001000,oo=1000000000;
int i,j,k,n,nb0,nb1,nm,ans,En,S,T;
int a[N],fg[M],pr[M/10],z[M];
int b0[N],b1[N],c[N],d[N],h[N];
struct edge { int s,n,v;} E[N*N];
void pre(int n) {
	int i,j;
	fg[1]=3;
	for (i=2;i<=n;i++) {
		if (fg[i]!=3) pr[++nm]=i,fg[i]=1;
		for (j=1;j<=nm;j++) {
			if (i*pr[j]>n) break;
			fg[i*pr[j]]=3;
			if (i%pr[j]==0) break;
		}
	}
	for (i=2;i<=n;i+=2) fg[i]=2;
}
void E_add(int x,int y,int v) {
	E[++En].s=y;E[En].v=v;
	E[En].n=h[x];h[x]=En;
	E[++En].s=x;E[En].v=0;
	E[En].n=h[y];h[y]=En;
}
bool bfs() {
	int i,j,k;
	memset(c,0,sizeof c);
	i=0;j=1;d[1]=S;c[S]=1;
	while (i<j) {
		i++;
		for (k=h[d[i]];k;k=E[k].n) if (E[k].v && !c[E[k].s]) {
			c[E[k].s]=c[d[i]]+1;
			d[++j]=E[k].s;
		}
	}
	return c[T];
}
int dfs(int x,int y) {
	if (x==T || !y) return y;
	int k,t,Y=y;
	for (k=h[x];k;k=E[k].n) if (E[k].v && c[x]+1==c[E[k].s]) {
		t=dfs(E[k].s,min(E[k].v,y));
		y-=t;
		E[k].v-=t;
		E[k^1].v+=t;
		if (!y) return Y;
	}
	if (Y==y) c[x]=-1;
	return Y-y;
}
int main() {
	scanf("%d",&n);
	for (i=1;i<=n;i++) scanf("%d",&a[i]);
	pre(a[n]);
	for (i=1;i<=n;i++) z[a[i]]^=1,z[a[i]+1]^=1;
	for (i=1;i<=a[n]+1;i++) if (z[i]) {
		if (i&1) b1[++nb1]=i;
		else b0[++nb0]=i;
	}
	En=1;S=nb0+nb1+1;T=S+1;
	for (i=1;i<=nb0;i++) E_add(S,i,1);
	for (j=1;j<=nb1;j++) E_add(nb0+j,T,1);
	for (i=1;i<=nb0;i++)
		for (j=1;j<=nb1;j++) {
			k=b0[i]-b1[j];
			if (k<0) k=-k;
			if (fg[k]==1) E_add(i,nb0+j,1);
		}
	while (bfs()) ans+=dfs(S,oo);
	nb0-=ans;
	nb1-=ans;
	ans+=nb0/2*2+nb1/2*2;
	nb0&=1;nb1&=1;
	if (nb0) ans+=3;
	printf("%d\n",ans);
}
### Prompt

Develop a solution in CPP to the problem described below:

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;
const int N=220,M=10001000,oo=1000000000;
int i,j,k,n,nb0,nb1,nm,ans,En,S,T;
int a[N],fg[M],pr[M/10],z[M];
int b0[N],b1[N],c[N],d[N],h[N];
struct edge { int s,n,v;} E[N*N];
void pre(int n) {
	int i,j;
	fg[1]=3;
	for (i=2;i<=n;i++) {
		if (fg[i]!=3) pr[++nm]=i,fg[i]=1;
		for (j=1;j<=nm;j++) {
			if (i*pr[j]>n) break;
			fg[i*pr[j]]=3;
			if (i%pr[j]==0) break;
		}
	}
	for (i=2;i<=n;i+=2) fg[i]=2;
}
void E_add(int x,int y,int v) {
	E[++En].s=y;E[En].v=v;
	E[En].n=h[x];h[x]=En;
	E[++En].s=x;E[En].v=0;
	E[En].n=h[y];h[y]=En;
}
bool bfs() {
	int i,j,k;
	memset(c,0,sizeof c);
	i=0;j=1;d[1]=S;c[S]=1;
	while (i<j) {
		i++;
		for (k=h[d[i]];k;k=E[k].n) if (E[k].v && !c[E[k].s]) {
			c[E[k].s]=c[d[i]]+1;
			d[++j]=E[k].s;
		}
	}
	return c[T];
}
int dfs(int x,int y) {
	if (x==T || !y) return y;
	int k,t,Y=y;
	for (k=h[x];k;k=E[k].n) if (E[k].v && c[x]+1==c[E[k].s]) {
		t=dfs(E[k].s,min(E[k].v,y));
		y-=t;
		E[k].v-=t;
		E[k^1].v+=t;
		if (!y) return Y;
	}
	if (Y==y) c[x]=-1;
	return Y-y;
}
int main() {
	scanf("%d",&n);
	for (i=1;i<=n;i++) scanf("%d",&a[i]);
	pre(a[n]);
	for (i=1;i<=n;i++) z[a[i]]^=1,z[a[i]+1]^=1;
	for (i=1;i<=a[n]+1;i++) if (z[i]) {
		if (i&1) b1[++nb1]=i;
		else b0[++nb0]=i;
	}
	En=1;S=nb0+nb1+1;T=S+1;
	for (i=1;i<=nb0;i++) E_add(S,i,1);
	for (j=1;j<=nb1;j++) E_add(nb0+j,T,1);
	for (i=1;i<=nb0;i++)
		for (j=1;j<=nb1;j++) {
			k=b0[i]-b1[j];
			if (k<0) k=-k;
			if (fg[k]==1) E_add(i,nb0+j,1);
		}
	while (bfs()) ans+=dfs(S,oo);
	nb0-=ans;
	nb1-=ans;
	ans+=nb0/2*2+nb1/2*2;
	nb0&=1;nb1&=1;
	if (nb0) ans+=3;
	printf("%d\n",ans);
}
```