#include <bits/stdc++.h>
using namespace std;
const int N = 10000010;
bool pd[N];
int prime[N],tot;
void find_prime(){
	memset(pd,true,sizeof(pd));
	for(int i=2;i<N;i++){
		if(pd[i]) prime[++tot]=i;
		for(int j=1;j<=tot;j++){
			if(prime[j]*i>=N) break;
			pd[prime[j]*i]=false;
			if(i%prime[j]==0) break;
		}
	}
	pd[0] = pd[1]=pd[2]=false;
}
bool pd2[N];
int n,a[110];
vector<int> v[2];
vector<int> g[300];
bool flag[300];
int last[300];
bool find(int x){
	int t;
	for(int i = 0;i<g[x].size();i++) if(flag[t=g[x][i]]){
		flag[t] = false;
		if(last[t]==0) {
			last[t] = x+1;
			return true;
		} else if(find(last[t]-1)){
			last[t] = x+1;
			return true;
		}
	}
	return false;
}
int main(){
	find_prime();
	scanf("%d",&n);
	for(int i = 1;i<=n;i++)scanf("%d",a+i),pd2[a[i]]=true;
	for(int i = 1;i<N;i++) if(pd2[i]!=pd2[i-1]) v[i&1].push_back(i);
	for(int i = 0;i<v[0].size();i++){
		for(int j = 0;j<v[1].size();j++){
			if(pd[abs(v[0][i]-v[1][j])]) g[i].push_back(j);//puts("YYY");
		}
	}
	int tot = 0;
	//for(int i = 0;i<v[1].size();i++) cout<<v[1][i]<<endl;
	for(int i = 0;i<v[0].size();i++) {
		memset(flag,true,sizeof(flag));	
		if(find(i)) tot++;
	}
	//cout<<tot<<endl;
	printf("%d\n",tot+(v[0].size()-tot)/2*2+(v[1].size()-tot)/2*2+(v[0].size()-tot)%2*3);
	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>
using namespace std;
const int N = 10000010;
bool pd[N];
int prime[N],tot;
void find_prime(){
	memset(pd,true,sizeof(pd));
	for(int i=2;i<N;i++){
		if(pd[i]) prime[++tot]=i;
		for(int j=1;j<=tot;j++){
			if(prime[j]*i>=N) break;
			pd[prime[j]*i]=false;
			if(i%prime[j]==0) break;
		}
	}
	pd[0] = pd[1]=pd[2]=false;
}
bool pd2[N];
int n,a[110];
vector<int> v[2];
vector<int> g[300];
bool flag[300];
int last[300];
bool find(int x){
	int t;
	for(int i = 0;i<g[x].size();i++) if(flag[t=g[x][i]]){
		flag[t] = false;
		if(last[t]==0) {
			last[t] = x+1;
			return true;
		} else if(find(last[t]-1)){
			last[t] = x+1;
			return true;
		}
	}
	return false;
}
int main(){
	find_prime();
	scanf("%d",&n);
	for(int i = 1;i<=n;i++)scanf("%d",a+i),pd2[a[i]]=true;
	for(int i = 1;i<N;i++) if(pd2[i]!=pd2[i-1]) v[i&1].push_back(i);
	for(int i = 0;i<v[0].size();i++){
		for(int j = 0;j<v[1].size();j++){
			if(pd[abs(v[0][i]-v[1][j])]) g[i].push_back(j);//puts("YYY");
		}
	}
	int tot = 0;
	//for(int i = 0;i<v[1].size();i++) cout<<v[1][i]<<endl;
	for(int i = 0;i<v[0].size();i++) {
		memset(flag,true,sizeof(flag));	
		if(find(i)) tot++;
	}
	//cout<<tot<<endl;
	printf("%d\n",tot+(v[0].size()-tot)/2*2+(v[1].size()-tot)/2*2+(v[0].size()-tot)%2*3);
	return 0;
}
```