#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
typedef pair<ll,ll> pll;
void read(int& x){ scanf("%d",&x); }
void read(ll& x){ scanf("%lld",&x); }
template<typename T,typename... Args>
void read(T& a,Args&... b){ read(a); read(b...); }
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define eb emplace_back
#define x first
#define y second
 
int n;
int p[210];
 
void in(){
	int t; read(t);
	int last;
	read(last);
	p[++n] = last;
	for(;--t;){
		int x; read(x);
		if(last+1 < x){
			p[++n] = last+1;
			p[++n] = x;
		}
		last = x;
	}
	p[++n] = last+1;
}
 
bool is_prime(int x){
	if(x==1) return 0;
	if(x==2) return 0;
	for(int i=2; i*i<=x; ++i) if(x%i==0) return 0;
	return 1;
}
vector<int>edge[210];
int vis[210];
int rev[210];
 
bool dfs(int x){
	if(vis[x]) return 0;
	vis[x]=1;
	for(int y:edge[x]){
		if(!rev[y] || dfs(rev[y])){
			rev[y]=x;
			return 1;
		}
	}
	return 0;
}
 
int MM(){ int ret = 0;
	for(int i=1; i<=n; ++i){
		fill(vis+1, vis+n+1, 0);
		if(dfs(i)) ret += 1;
	}
	return ret;
}
 
int main()
{
	in();
	int oc=0, ec=0;
	for(int i=1; i<=n; ++i){
		((p[i]%2)?oc:ec)++;
		for(int j=i+1; j<=n; ++j){
			if(is_prime(p[j]-p[i])){
				int a=i, b=j;
				if(p[a]%2) swap(a, b);
				edge[a].pb(b);
			}
		}
	}
	int mm = MM();
	int ans = 2e9;
	for(int pu=0; pu<=mm; ++pu){
		int cur = 0;
		cur += (oc-pu)/2*2;
		cur += (ec-pu)/2*2;
		cur += ((oc-pu)%2)*((ec-pu)%2)*3;
		cur += pu;
		ans = min(ans, cur);
	}
	printf("%d\n", ans);
	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;
typedef long long ll;
typedef pair<int,int> pp;
typedef pair<ll,ll> pll;
void read(int& x){ scanf("%d",&x); }
void read(ll& x){ scanf("%lld",&x); }
template<typename T,typename... Args>
void read(T& a,Args&... b){ read(a); read(b...); }
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define eb emplace_back
#define x first
#define y second
 
int n;
int p[210];
 
void in(){
	int t; read(t);
	int last;
	read(last);
	p[++n] = last;
	for(;--t;){
		int x; read(x);
		if(last+1 < x){
			p[++n] = last+1;
			p[++n] = x;
		}
		last = x;
	}
	p[++n] = last+1;
}
 
bool is_prime(int x){
	if(x==1) return 0;
	if(x==2) return 0;
	for(int i=2; i*i<=x; ++i) if(x%i==0) return 0;
	return 1;
}
vector<int>edge[210];
int vis[210];
int rev[210];
 
bool dfs(int x){
	if(vis[x]) return 0;
	vis[x]=1;
	for(int y:edge[x]){
		if(!rev[y] || dfs(rev[y])){
			rev[y]=x;
			return 1;
		}
	}
	return 0;
}
 
int MM(){ int ret = 0;
	for(int i=1; i<=n; ++i){
		fill(vis+1, vis+n+1, 0);
		if(dfs(i)) ret += 1;
	}
	return ret;
}
 
int main()
{
	in();
	int oc=0, ec=0;
	for(int i=1; i<=n; ++i){
		((p[i]%2)?oc:ec)++;
		for(int j=i+1; j<=n; ++j){
			if(is_prime(p[j]-p[i])){
				int a=i, b=j;
				if(p[a]%2) swap(a, b);
				edge[a].pb(b);
			}
		}
	}
	int mm = MM();
	int ans = 2e9;
	for(int pu=0; pu<=mm; ++pu){
		int cur = 0;
		cur += (oc-pu)/2*2;
		cur += (ec-pu)/2*2;
		cur += ((oc-pu)%2)*((ec-pu)%2)*3;
		cur += pu;
		ans = min(ans, cur);
	}
	printf("%d\n", ans);
	return 0;
}
```