#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<bitset>
#include<map>

#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)

using namespace std;

typedef long long LL;
typedef double db;

int get(){
	char ch;
	while(ch=getchar(),(ch<'0'||ch>'9')&&ch!='-');
	if (ch=='-'){
		int s=0;
		while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';
		return -s;
	}
	int s=ch-'0';
	while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';
	return s;
}

const int N = 205;
const int L = 1e+7+10;

int n;
int b[L];
int a[N];
int pri[L],m;
bool bz[L];
int X[N],Y[N],kx,ky;
int fa[N],e[N][N];
int vis[N],tim;

bool can(int x){
	if (vis[x]==tim)return 0;
	vis[x]=tim;
	fo(i,1,e[x][0]){
		int y=e[x][i];
		if (!fa[y]||can(fa[y])){
			fa[y]=x;
			return 1;
		}
	}
	return 0;
}

int main(){
	n=get();
	fo(i,1,n){
		int x=get();
		b[x-1]^=1;b[x]^=1;
	}
	int k=0;
	fo(i,0,1e+7)
	if (b[i])a[++k]=i;
	fo(i,2,1e+7){
		if (!bz[i])pri[++m]=i;
		fo(j,1,m){
			if (1ll*i*pri[j]>1e+7)break;
			bz[i*pri[j]]=1;
			if (i%pri[j]==0)break;
		}
	}
	bz[1]=bz[2]=1;
	fo(i,1,k)
	if (a[i]&1)X[++kx]=a[i];else Y[++ky]=a[i];
	fo(i,1,kx)
		fo(j,1,ky)
		if (!bz[abs(X[i]-Y[j])])e[i][++e[i][0]]=j;
	int cnt=0;
	fo(i,1,kx){
		tim++;
		if (can(i))cnt++;
	}
	int ans=cnt+((kx-cnt)/2+(ky-cnt)/2)*2+((kx-cnt)%2)*3;
	printf("%d\n",ans);
	return 0;
}
### Prompt

Please provide a CPP coded solution 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<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<bitset>
#include<map>

#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)

using namespace std;

typedef long long LL;
typedef double db;

int get(){
	char ch;
	while(ch=getchar(),(ch<'0'||ch>'9')&&ch!='-');
	if (ch=='-'){
		int s=0;
		while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';
		return -s;
	}
	int s=ch-'0';
	while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';
	return s;
}

const int N = 205;
const int L = 1e+7+10;

int n;
int b[L];
int a[N];
int pri[L],m;
bool bz[L];
int X[N],Y[N],kx,ky;
int fa[N],e[N][N];
int vis[N],tim;

bool can(int x){
	if (vis[x]==tim)return 0;
	vis[x]=tim;
	fo(i,1,e[x][0]){
		int y=e[x][i];
		if (!fa[y]||can(fa[y])){
			fa[y]=x;
			return 1;
		}
	}
	return 0;
}

int main(){
	n=get();
	fo(i,1,n){
		int x=get();
		b[x-1]^=1;b[x]^=1;
	}
	int k=0;
	fo(i,0,1e+7)
	if (b[i])a[++k]=i;
	fo(i,2,1e+7){
		if (!bz[i])pri[++m]=i;
		fo(j,1,m){
			if (1ll*i*pri[j]>1e+7)break;
			bz[i*pri[j]]=1;
			if (i%pri[j]==0)break;
		}
	}
	bz[1]=bz[2]=1;
	fo(i,1,k)
	if (a[i]&1)X[++kx]=a[i];else Y[++ky]=a[i];
	fo(i,1,kx)
		fo(j,1,ky)
		if (!bz[abs(X[i]-Y[j])])e[i][++e[i][0]]=j;
	int cnt=0;
	fo(i,1,kx){
		tim++;
		if (can(i))cnt++;
	}
	int ans=cnt+((kx-cnt)/2+(ky-cnt)/2)*2+((kx-cnt)%2)*3;
	printf("%d\n",ans);
	return 0;
}
```