#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#define N 210
#define M 10000010
using namespace std;
struct edge{int x, y, next;}a[40010];
int T, n, l, p[M], flag[M], w[N], x, l1, l2, a1[N], a2[N], F[N], match[N], P[N], k, ans, ss;
map<int, int>mp;
map<int, int>::iterator it;
inline void prev(){
	l=0; memset(flag, 0, sizeof(flag)); flag[1]=1;
	for(int i=2; i<=10000000; i++){
		if(!flag[i])p[++l]=i;
		for(int j=1; j<=l&&i*p[j]<=10000000; j++){
			flag[i*p[j]]=1; if(i%p[j]==0)break;
		}
	}
}
inline int ABS(int x){return x>0?x:-x;}
inline void add(int x, int y){a[++l].x=x; a[l].y=y; a[l].next=P[x]; P[x]=l;}
inline int dfs(int x){
	for(int i=P[x]; i; i=a[i].next)if(F[a[i].y]<ss){
		F[a[i].y]=ss; if(!match[a[i].y]||dfs(match[a[i].y])){match[a[i].y]=x; return 1;}
	}
	return 0;
}
int main(){
	prev();
	T=1;
	for(int owo=1; owo<=T; owo++){
		scanf("%d", &n); l1=l2=0; mp.clear();
		for(int i=1; i<=n; i++){scanf("%d", &x); mp[x]^=1; mp[x+1]^=1;}
		for(it=mp.begin(); it!=mp.end(); it++)if(it->second){
			x=it->first;
			if(x&1)a1[++l1]=x; else a2[++l2]=x;
		}
		l=0; memset(P, 0, sizeof(P));
		for(int i=1; i<=l1; i++)
			for(int j=1; j<=l2; j++)if(!flag[ABS(a1[i]-a2[j])])add(i, j);
		k=ss=0; memset(F, 0, sizeof(F)); memset(match, 0, sizeof(match));
		for(int i=1; i<=l1; i++){ss++; k+=dfs(i);}
		ans=k+((l1-k)/2+(l2-k)/2)*2+((l1-k)%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<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#define N 210
#define M 10000010
using namespace std;
struct edge{int x, y, next;}a[40010];
int T, n, l, p[M], flag[M], w[N], x, l1, l2, a1[N], a2[N], F[N], match[N], P[N], k, ans, ss;
map<int, int>mp;
map<int, int>::iterator it;
inline void prev(){
	l=0; memset(flag, 0, sizeof(flag)); flag[1]=1;
	for(int i=2; i<=10000000; i++){
		if(!flag[i])p[++l]=i;
		for(int j=1; j<=l&&i*p[j]<=10000000; j++){
			flag[i*p[j]]=1; if(i%p[j]==0)break;
		}
	}
}
inline int ABS(int x){return x>0?x:-x;}
inline void add(int x, int y){a[++l].x=x; a[l].y=y; a[l].next=P[x]; P[x]=l;}
inline int dfs(int x){
	for(int i=P[x]; i; i=a[i].next)if(F[a[i].y]<ss){
		F[a[i].y]=ss; if(!match[a[i].y]||dfs(match[a[i].y])){match[a[i].y]=x; return 1;}
	}
	return 0;
}
int main(){
	prev();
	T=1;
	for(int owo=1; owo<=T; owo++){
		scanf("%d", &n); l1=l2=0; mp.clear();
		for(int i=1; i<=n; i++){scanf("%d", &x); mp[x]^=1; mp[x+1]^=1;}
		for(it=mp.begin(); it!=mp.end(); it++)if(it->second){
			x=it->first;
			if(x&1)a1[++l1]=x; else a2[++l2]=x;
		}
		l=0; memset(P, 0, sizeof(P));
		for(int i=1; i<=l1; i++)
			for(int j=1; j<=l2; j++)if(!flag[ABS(a1[i]-a2[j])])add(i, j);
		k=ss=0; memset(F, 0, sizeof(F)); memset(match, 0, sizeof(match));
		for(int i=1; i<=l1; i++){ss++; k+=dfs(i);}
		ans=k+((l1-k)/2+(l2-k)/2)*2+((l1-k)%2)*3;
		printf("%d\n", ans);
	}
	return 0;
}
```