#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define ll long long
//{{{ read()
inline int read(){
	register int x=0,f=1;
	register char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')	f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')	x=x*10+(ch^48),ch=getchar();
	return x*f;
}
//}}}
const int N=1e7+5;
int n,mx,cnt,ans,now,las,a[N],mc[N],vs[N],vi[N];
bool dfs(int x,int tg){
	if(vs[x]==tg) return false;
	else	vs[x]=tg;
	for(int i=1;i<=cnt;i++)
		if(!vi[abs(a[x]-a[i])]&&(!mc[i]||dfs(mc[i],tg))){
			mc[i]=x; return true;
		}
	return false;
}
int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	n=read();
	for(int i=1;i<=n;i++){
		int x=read();
		if(!las) a[++cnt]=x;
		else	if(x!=las+1){
			a[++cnt]=x;
			a[++cnt]=las+1;
		}
		las=x;
	}
	a[++cnt]=las+1,mx=las+1,vi[0]=vi[1]=1;
	for(int i=2;i<=mx;i++){
		if(vi[i]) continue;
		for(int j=i*2;j<=mx;j+=i) vi[j]=1;
	} vi[2]=1;
	for(int i=1;i<=cnt;i++)
		if(a[i]&1) ans+=dfs(i,i);
	int A=-ans,B=-ans;
	for(int i=1;i<=cnt;i++)
		if(a[i]&1) ++A;
		else	++B;
	if(A&1)	ans+=3;
	ans+=A/2*2+B/2*2;
	printf("%d\n",ans);
	return 0;
}

### Prompt

Your task is to create 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<algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define ll long long
//{{{ read()
inline int read(){
	register int x=0,f=1;
	register char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')	f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')	x=x*10+(ch^48),ch=getchar();
	return x*f;
}
//}}}
const int N=1e7+5;
int n,mx,cnt,ans,now,las,a[N],mc[N],vs[N],vi[N];
bool dfs(int x,int tg){
	if(vs[x]==tg) return false;
	else	vs[x]=tg;
	for(int i=1;i<=cnt;i++)
		if(!vi[abs(a[x]-a[i])]&&(!mc[i]||dfs(mc[i],tg))){
			mc[i]=x; return true;
		}
	return false;
}
int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	n=read();
	for(int i=1;i<=n;i++){
		int x=read();
		if(!las) a[++cnt]=x;
		else	if(x!=las+1){
			a[++cnt]=x;
			a[++cnt]=las+1;
		}
		las=x;
	}
	a[++cnt]=las+1,mx=las+1,vi[0]=vi[1]=1;
	for(int i=2;i<=mx;i++){
		if(vi[i]) continue;
		for(int j=i*2;j<=mx;j+=i) vi[j]=1;
	} vi[2]=1;
	for(int i=1;i<=cnt;i++)
		if(a[i]&1) ans+=dfs(i,i);
	int A=-ans,B=-ans;
	for(int i=1;i<=cnt;i++)
		if(a[i]&1) ++A;
		else	++B;
	if(A&1)	ans+=3;
	ans+=A/2*2+B/2*2;
	printf("%d\n",ans);
	return 0;
}

```