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

const int N=110;
int n,lL[N],lR[N],mL[N],mR[N],vis[N],g[N][N],ans,nl,nr;
set<int>L,R;
bool is_prime(int x){
	if(x==1)return 0;
	for(int i=2;i*i<=x;++i)if(x%i==0)return 0;
	return 1;
}

void ins(int x){
	if(x&1){if(L.count(x))L.erase(x);else L.insert(x);}
	else{if(R.count(x))R.erase(x);else R.insert(x);}
}

int dfs(int x){
	for(int i=1;i<=nr;++i)if(!vis[i]&&g[x][i]){
		vis[i]=1;
		if(!mL[i]||dfs(mL[i])){mL[i]=x;mR[x]=i;return 1;}
	}
	return 0;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;++i){int x;cin>>x;ins(x);ins(x+1);}
	for(int i:L)lL[++nl]=i;for(int i:R)lR[++nr]=i;
	for(int i=1;i<=nl;++i)
		for(int j=1;j<=nr;++j)
			g[i][j]=is_prime(abs(lL[i]-lR[j]));
	for(int i=1;i<=nl;++i)if(!mR[i]){
		memset(vis,0,sizeof vis);
		if(dfs(i))++ans;
	}
	nl-=ans;nr-=ans;
	ans+=nl/2*2+nr/2*2;
	nl%=2;nr%=2;
	assert(nl==nr);
	ans+=nl*3;
	cout<<ans<<'\n';
	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=110;
int n,lL[N],lR[N],mL[N],mR[N],vis[N],g[N][N],ans,nl,nr;
set<int>L,R;
bool is_prime(int x){
	if(x==1)return 0;
	for(int i=2;i*i<=x;++i)if(x%i==0)return 0;
	return 1;
}

void ins(int x){
	if(x&1){if(L.count(x))L.erase(x);else L.insert(x);}
	else{if(R.count(x))R.erase(x);else R.insert(x);}
}

int dfs(int x){
	for(int i=1;i<=nr;++i)if(!vis[i]&&g[x][i]){
		vis[i]=1;
		if(!mL[i]||dfs(mL[i])){mL[i]=x;mR[x]=i;return 1;}
	}
	return 0;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;++i){int x;cin>>x;ins(x);ins(x+1);}
	for(int i:L)lL[++nl]=i;for(int i:R)lR[++nr]=i;
	for(int i=1;i<=nl;++i)
		for(int j=1;j<=nr;++j)
			g[i][j]=is_prime(abs(lL[i]-lR[j]));
	for(int i=1;i<=nl;++i)if(!mR[i]){
		memset(vis,0,sizeof vis);
		if(dfs(i))++ans;
	}
	nl-=ans;nr-=ans;
	ans+=nl/2*2+nr/2*2;
	nl%=2;nr%=2;
	assert(nl==nr);
	ans+=nl*3;
	cout<<ans<<'\n';
	return 0;
}
```