#include<bits/stdc++.h>
using namespace std;

bool up[10000002];
vector<int> v1;
vector<int> v2;

int Nx,Ny;
const int MAXN = 200;
vector<int> edgex[MAXN+1],edgey[MAXN+1];
int matchx[MAXN+1],matchy[MAXN+1];
bool visitx[MAXN+1],visity[MAXN+1];
bool dfs(int x){
   visitx[x]=true;
   for(int i=0;i<edgex[x].size();i++){
      int y=edgex[x][i];
      visity[y]=true;
      if(matchy[y]==-1||(!visitx[matchy[y]]&&dfs(matchy[y]))){
         matchy[matchx[x]=y]=x;
         return true;
      }
   }
   return false;
}
int matching(){
   memset(matchx,-1,sizeof matchx);
   memset(matchy,-1,sizeof matchy);
   int ans=0;
   for(int i=0;i<Nx;i++){
      memset(visitx,0,sizeof visitx);
      memset(visity,0,sizeof visity);
      if(dfs(i))  ans++;
   }
   return ans;
}
bool op(int x,int y){
	int tmp=abs(x-y);
	if(tmp==1||tmp==2)	return false;
	for(long long int i=3;i*i<=tmp;i++)
		if(tmp%i==0)
			return false;
	return true;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin>>n;
	for(int i=0,x;i<n;i++){
		cin>>x;
		up[x]=true;
	}
	for(int i=1;i<=10000001;i++)
		if(up[i]!=up[i-1]){
			if(i&1)
				v1.push_back(i);
			else
				v2.push_back(i);
		}
	Nx=v1.size();Ny=v2.size();
	for(int i=0;i<Nx;i++)
		for(int j=0;j<Ny;j++)
			if(op(v1[i],v2[j]))
				edgex[i].push_back(j),edgey[j].push_back(i);
	int k=matching();
	cout<<k+(Nx-k)/2*2+(Ny-k)/2*2+3*((Nx-k)&1)<<endl;
}
### 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;

bool up[10000002];
vector<int> v1;
vector<int> v2;

int Nx,Ny;
const int MAXN = 200;
vector<int> edgex[MAXN+1],edgey[MAXN+1];
int matchx[MAXN+1],matchy[MAXN+1];
bool visitx[MAXN+1],visity[MAXN+1];
bool dfs(int x){
   visitx[x]=true;
   for(int i=0;i<edgex[x].size();i++){
      int y=edgex[x][i];
      visity[y]=true;
      if(matchy[y]==-1||(!visitx[matchy[y]]&&dfs(matchy[y]))){
         matchy[matchx[x]=y]=x;
         return true;
      }
   }
   return false;
}
int matching(){
   memset(matchx,-1,sizeof matchx);
   memset(matchy,-1,sizeof matchy);
   int ans=0;
   for(int i=0;i<Nx;i++){
      memset(visitx,0,sizeof visitx);
      memset(visity,0,sizeof visity);
      if(dfs(i))  ans++;
   }
   return ans;
}
bool op(int x,int y){
	int tmp=abs(x-y);
	if(tmp==1||tmp==2)	return false;
	for(long long int i=3;i*i<=tmp;i++)
		if(tmp%i==0)
			return false;
	return true;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin>>n;
	for(int i=0,x;i<n;i++){
		cin>>x;
		up[x]=true;
	}
	for(int i=1;i<=10000001;i++)
		if(up[i]!=up[i-1]){
			if(i&1)
				v1.push_back(i);
			else
				v2.push_back(i);
		}
	Nx=v1.size();Ny=v2.size();
	for(int i=0;i<Nx;i++)
		for(int j=0;j<Ny;j++)
			if(op(v1[i],v2[j]))
				edgex[i].push_back(j),edgey[j].push_back(i);
	int k=matching();
	cout<<k+(Nx-k)/2*2+(Ny-k)/2*2+3*((Nx-k)&1)<<endl;
}
```