#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<stack>
#include<cmath>
#include<map>
#include<complex>
#define rep(i,l,r) for (int i=l;i<=r;i++)
#define down(i,l,r) for (int i=l;i>=r;i--)
#define clr(x,y) memset(x,y,sizeof(x))
#define maxn 320500
#define inf (int)1e9
#define ll long long
#define mm 1000000007
#define eps 1e-13
#define pb push_back
#define low(x) x&(-x)
using namespace std;

ll read(){
    ll x=0,f=1; char ch=getchar();
    while (!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
int a[805],b[805];
int matl[405],lnk[405],matr[405],q[2005000],visb[405],lk[405],slack[405];
int mp[10000005],pmp[10000005],vis[10000005],pri[1000500];
int ans,ptot,n,m,idx,la,lb;
bool fd(int x){
	rep(j,1,lb){
		if (!visb[j]&&pmp[abs(a[x]-b[j])]){
			visb[j]=1;
			if (lk[j]==-1||fd(lk[j])){
				lk[j]=x;
				return 1;
			}
		}
	}
	return 0;
}
int main(){
//	freopen("input.txt","r",stdin);
//	freopen("output.txt","w",stdout);
	n=read();
	int mxn=10000001;
	int x;
	rep(i,1,n) x=read(),mp[x]=1;
	//rep(i,1,n) if (mp[a[i]-1]==mp[a[i]]) b[i]=0; else b[i]=1;
	rep(i,0,x) if (mp[i]!=mp[i+1]) {
		if (i%2==0) a[++la]=i; else b[++lb]=i;
	}
	rep(i,2,mxn) {
		if (!vis[i]) pri[++ptot]=i,vis[i]=1,pmp[i]=1;
		rep(j,1,ptot) {
			if (i*pri[j]>mxn) break;
			vis[i*pri[j]]=1;
		}
	}
	clr(lk,-1);
	int ans=0;
	rep(i,1,la) {
		clr(visb,0);
		if (fd(i)) ans++;
	}
	la-=ans;
	lb-=ans;
	if (la%2==1) ans+=3;
	ans+=la/2*2+lb/2*2;
	printf("%d\n",ans);
	return 0;
}
### Prompt

Create a solution in cpp for 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<cstring>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<stack>
#include<cmath>
#include<map>
#include<complex>
#define rep(i,l,r) for (int i=l;i<=r;i++)
#define down(i,l,r) for (int i=l;i>=r;i--)
#define clr(x,y) memset(x,y,sizeof(x))
#define maxn 320500
#define inf (int)1e9
#define ll long long
#define mm 1000000007
#define eps 1e-13
#define pb push_back
#define low(x) x&(-x)
using namespace std;

ll read(){
    ll x=0,f=1; char ch=getchar();
    while (!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
int a[805],b[805];
int matl[405],lnk[405],matr[405],q[2005000],visb[405],lk[405],slack[405];
int mp[10000005],pmp[10000005],vis[10000005],pri[1000500];
int ans,ptot,n,m,idx,la,lb;
bool fd(int x){
	rep(j,1,lb){
		if (!visb[j]&&pmp[abs(a[x]-b[j])]){
			visb[j]=1;
			if (lk[j]==-1||fd(lk[j])){
				lk[j]=x;
				return 1;
			}
		}
	}
	return 0;
}
int main(){
//	freopen("input.txt","r",stdin);
//	freopen("output.txt","w",stdout);
	n=read();
	int mxn=10000001;
	int x;
	rep(i,1,n) x=read(),mp[x]=1;
	//rep(i,1,n) if (mp[a[i]-1]==mp[a[i]]) b[i]=0; else b[i]=1;
	rep(i,0,x) if (mp[i]!=mp[i+1]) {
		if (i%2==0) a[++la]=i; else b[++lb]=i;
	}
	rep(i,2,mxn) {
		if (!vis[i]) pri[++ptot]=i,vis[i]=1,pmp[i]=1;
		rep(j,1,ptot) {
			if (i*pri[j]>mxn) break;
			vis[i*pri[j]]=1;
		}
	}
	clr(lk,-1);
	int ans=0;
	rep(i,1,la) {
		clr(visb,0);
		if (fd(i)) ans++;
	}
	la-=ans;
	lb-=ans;
	if (la%2==1) ans+=3;
	ans+=la/2*2+lb/2*2;
	printf("%d\n",ans);
	return 0;
}
```