#include<bits/stdc++.h>
using namespace std;
#define N 1116
#define M 111116
#define inf 1111111116
#define next nxt
 
int n,k,a[M],b[M],f[M],next[M],p[N],now[N],d[N],h[N],cnt,ans;
vector<int> x;
queue<int> q;
 
void add(int x,int y){
	a[++k]=x;b[k]=y;f[k]=1;next[k]=p[x];p[x]=k;
	a[++k]=y;b[k]=x;f[k]=0;next[k]=p[y];p[y]=k;
}
 
bool travel(){
	memcpy(now,p,sizeof(p));
	fill(d+1,d+n+3,inf);d[n+1]=0;
	q.push(n+1);h[n+1]=1;
	while (!q.empty()){
		int x=q.front();q.pop();h[x]=0;
		for (int t=p[x];t;t=next[t])
			if (f[t]&&d[x]+1<d[b[t]]){
				d[b[t]]=d[x]+1;
				if (!h[b[t]]) q.push(b[t]),h[b[t]]=1;
			}
	}
	return d[n+2]<inf;
}
 
int dinic(int x,int lmt){
	if (x==n+2) return lmt;int cnt=0;
	for (int t=now[x];t;t=now[x]=next[t])
		if (f[t]&&d[x]<d[b[t]]){
			int tmp=dinic(b[t],min(f[t],lmt-cnt));
			f[t]-=tmp;f[t^1]+=tmp;cnt+=tmp;
			if (cnt==lmt) return lmt;
		}
	return cnt;
}
 
bool check(int x){
	if (x%2==0||x==1) return false;
	for (int i=2;i*i<=x;i++)
		if (x%i==0) return false;
	return true;
}
 
int read(){
	int x=0,f=1;char ch=getchar();
	for (;!isdigit(ch);ch=getchar()) if (ch=='-')  f=-f;
	for (;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
	return x*f;
}
 
int main(){
	n=read();k=1;x.push_back(0);
	for (int i=1;i<=n;i++){
		int t=read();
		if (x.back()==t) x.pop_back();
		else x.push_back(t);
		x.push_back(t+1);
	}
	n=x.size()-1;
	for (int i=1;i<=n;i++)
		if (x[i]&1) add(n+1,i),cnt++;
		else {
			for (int j=1;j<=n;j++)
				if (check(abs(x[i]-x[j]))) add(j,i);
			add(i,n+2);
		}
	while (travel()) ans+=dinic(n+1,inf);
	printf("%d\n",n-ans+(cnt-ans)%2);
	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<bits/stdc++.h>
using namespace std;
#define N 1116
#define M 111116
#define inf 1111111116
#define next nxt
 
int n,k,a[M],b[M],f[M],next[M],p[N],now[N],d[N],h[N],cnt,ans;
vector<int> x;
queue<int> q;
 
void add(int x,int y){
	a[++k]=x;b[k]=y;f[k]=1;next[k]=p[x];p[x]=k;
	a[++k]=y;b[k]=x;f[k]=0;next[k]=p[y];p[y]=k;
}
 
bool travel(){
	memcpy(now,p,sizeof(p));
	fill(d+1,d+n+3,inf);d[n+1]=0;
	q.push(n+1);h[n+1]=1;
	while (!q.empty()){
		int x=q.front();q.pop();h[x]=0;
		for (int t=p[x];t;t=next[t])
			if (f[t]&&d[x]+1<d[b[t]]){
				d[b[t]]=d[x]+1;
				if (!h[b[t]]) q.push(b[t]),h[b[t]]=1;
			}
	}
	return d[n+2]<inf;
}
 
int dinic(int x,int lmt){
	if (x==n+2) return lmt;int cnt=0;
	for (int t=now[x];t;t=now[x]=next[t])
		if (f[t]&&d[x]<d[b[t]]){
			int tmp=dinic(b[t],min(f[t],lmt-cnt));
			f[t]-=tmp;f[t^1]+=tmp;cnt+=tmp;
			if (cnt==lmt) return lmt;
		}
	return cnt;
}
 
bool check(int x){
	if (x%2==0||x==1) return false;
	for (int i=2;i*i<=x;i++)
		if (x%i==0) return false;
	return true;
}
 
int read(){
	int x=0,f=1;char ch=getchar();
	for (;!isdigit(ch);ch=getchar()) if (ch=='-')  f=-f;
	for (;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
	return x*f;
}
 
int main(){
	n=read();k=1;x.push_back(0);
	for (int i=1;i<=n;i++){
		int t=read();
		if (x.back()==t) x.pop_back();
		else x.push_back(t);
		x.push_back(t+1);
	}
	n=x.size()-1;
	for (int i=1;i<=n;i++)
		if (x[i]&1) add(n+1,i),cnt++;
		else {
			for (int j=1;j<=n;j++)
				if (check(abs(x[i]-x[j]))) add(j,i);
			add(i,n+2);
		}
	while (travel()) ans+=dinic(n+1,inf);
	printf("%d\n",n-ans+(cnt-ans)%2);
	return 0;
}
```