#include <bits/stdc++.h>
typedef long long ll;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,a) FOR(i,0,a)
	
using namespace std;
const int MAX_N=100,MAX_X=1e7;
int N;
int sto[2][MAX_N*2],ston[2];
vector<int> G[MAX_N*2];
bool used[MAX_N*2];
int pa[MAX_N*2];
bool isp[MAX_X+1];
bool dfs(int v){
	used[v]=true;
	for(auto e:G[v]){
		if (pa[e]==-1 || (!used[pa[e]] && dfs(pa[e]))){
			pa[v]=e;
			pa[e]=v;
			return true;
		}
	}
	return false;
}
int matching(){
	int ret=0;
	memset(pa,-1,sizeof(pa));
	REP(v,ston[0]){
		fill(used,used+ston[0]+ston[1],false);
		if (pa[v]==-1 && dfs(v)){
			ret++;
		}
	}
	return ret;
}
int main(){
	cin>>N;
	{
		vector<bool> a((int)1e7+2),b((int)1e7+1);
		REP(i,N){
			int x;
			cin>>x;
			a[x]=1;
		}
		REP(i,(int)1e7+1){
			b[i]=a[i]^a[i+1];
		}
		REP(i,(int)1e7+1){
			if (b[i]){
				if (i&1){
					sto[1][ston[1]]=i;
					ston[1]++;
				}else{
					sto[0][ston[0]]=i;
					ston[0]++;
				}
			}
		}
	}
	memset(isp,1,sizeof(isp));
	isp[0]=isp[1]=false;
	FOR(i,2,MAX_X+1){
		if (isp[i]){
			for(int j=i*2;j<=MAX_X;j+=i){
				isp[j]=false;
			}
		}
	}
	REP(i,ston[0]){
		REP(j,ston[1]){
			int n=abs(sto[0][i]-sto[1][j]);
			if (n%2 && isp[n]){
				G[i].push_back(j+ston[0]);
				G[j+ston[0]].push_back(i);
			}
		}
	}
	int mat=matching();
	int ans=mat+(ston[0]-mat)/2*2+(ston[1]-mat)/2*2;
	if ((ston[0]-mat)%2){
		ans+=3;
	}
	cout<<ans<<endl;
	
	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 <bits/stdc++.h>
typedef long long ll;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,a) FOR(i,0,a)
	
using namespace std;
const int MAX_N=100,MAX_X=1e7;
int N;
int sto[2][MAX_N*2],ston[2];
vector<int> G[MAX_N*2];
bool used[MAX_N*2];
int pa[MAX_N*2];
bool isp[MAX_X+1];
bool dfs(int v){
	used[v]=true;
	for(auto e:G[v]){
		if (pa[e]==-1 || (!used[pa[e]] && dfs(pa[e]))){
			pa[v]=e;
			pa[e]=v;
			return true;
		}
	}
	return false;
}
int matching(){
	int ret=0;
	memset(pa,-1,sizeof(pa));
	REP(v,ston[0]){
		fill(used,used+ston[0]+ston[1],false);
		if (pa[v]==-1 && dfs(v)){
			ret++;
		}
	}
	return ret;
}
int main(){
	cin>>N;
	{
		vector<bool> a((int)1e7+2),b((int)1e7+1);
		REP(i,N){
			int x;
			cin>>x;
			a[x]=1;
		}
		REP(i,(int)1e7+1){
			b[i]=a[i]^a[i+1];
		}
		REP(i,(int)1e7+1){
			if (b[i]){
				if (i&1){
					sto[1][ston[1]]=i;
					ston[1]++;
				}else{
					sto[0][ston[0]]=i;
					ston[0]++;
				}
			}
		}
	}
	memset(isp,1,sizeof(isp));
	isp[0]=isp[1]=false;
	FOR(i,2,MAX_X+1){
		if (isp[i]){
			for(int j=i*2;j<=MAX_X;j+=i){
				isp[j]=false;
			}
		}
	}
	REP(i,ston[0]){
		REP(j,ston[1]){
			int n=abs(sto[0][i]-sto[1][j]);
			if (n%2 && isp[n]){
				G[i].push_back(j+ston[0]);
				G[j+ston[0]].push_back(i);
			}
		}
	}
	int mat=matching();
	int ans=mat+(ston[0]-mat)/2*2+(ston[1]-mat)/2*2;
	if ((ston[0]-mat)%2){
		ans+=3;
	}
	cout<<ans<<endl;
	
	return 0;
}
```