#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pb push_back
#define reset(a,b) memset(a,b,sizeof a);
#define ALL(x) x.begin(),x.end()
#define debug(x) cout<<#x<<" = "<<(x)<<endl
#define sz(x) (int)(x.size())
#define lt(x) (int)(x.length())
#define MOD 1000000007 
#define mx 100003

bool p[10000003], ya[10000003];
// int x[103];
vector<int> prima;
vector<int> genap, ganjil;
int sama[103];
int sudah[103];

int dfs(int now){
	for(int j = 0; j < sz(ganjil); j++){
		if(sudah[j])
			continue;
		if(p[abs(genap[now] - ganjil[j])])
			continue;
		sudah[j] = true;
		if(sama[j] == -1 || dfs(sama[j])){
			sama[j] = now;
			return 1;
		}
	}
	return 0;
}


int match(){
	int ret = 0;
	for(int i = 0; i < sz(ganjil); i++)
		sama[i] = -1;
	for(int i = 0; i < sz(genap); i++){
		for(int j = 0; j < sz(ganjil); j++)
			sudah[j] = false;
		ret += dfs(i);
	}
	return ret;
}

int main(){
	p[1] = true;
	for(int i = 2; i <= 1e7 + 1; i++){
		if(p[i])
			continue;
		if(i > 2)
			prima.pb(i);
		for(int j = i + i; j <= 1e7 + 1; j += i)
			p[j] = true;
	}
	int n;
	cin >> n;	
	for(int i = 0; i < n; i++){
		int x;
		cin >> x;
		ya[x] = true;
	}
	for(int i = 1; i <= 1e7 + 1; i++){
		if(ya[i] ^ ya[i - 1]){
			if(i % 2 == 0)
				genap.pb(i);
			else ganjil.pb(i);
		}
	}
	// debug(sz(genap));
	// debug(sz(ganjil));
	// for(int i : genap)
	// 	debug(i);
	// for(int i : ganjil)
	// 	debug(i);
	int aa = match();
	int sisaGenap = sz(genap) - aa;
	int sisaGanjil = sz(ganjil) - aa;
	int jaw = aa + (sisaGenap / 2) * 2 + (sisaGanjil / 2) * 2;
	if(sisaGanjil % 2 > 0){
		assert(sisaGenap % 2 > 0);
		jaw += 3;
	}
	cout << jaw << endl;
}
### Prompt

Please create a solution in CPP to 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;
#define f first
#define s second
#define pb push_back
#define reset(a,b) memset(a,b,sizeof a);
#define ALL(x) x.begin(),x.end()
#define debug(x) cout<<#x<<" = "<<(x)<<endl
#define sz(x) (int)(x.size())
#define lt(x) (int)(x.length())
#define MOD 1000000007 
#define mx 100003

bool p[10000003], ya[10000003];
// int x[103];
vector<int> prima;
vector<int> genap, ganjil;
int sama[103];
int sudah[103];

int dfs(int now){
	for(int j = 0; j < sz(ganjil); j++){
		if(sudah[j])
			continue;
		if(p[abs(genap[now] - ganjil[j])])
			continue;
		sudah[j] = true;
		if(sama[j] == -1 || dfs(sama[j])){
			sama[j] = now;
			return 1;
		}
	}
	return 0;
}


int match(){
	int ret = 0;
	for(int i = 0; i < sz(ganjil); i++)
		sama[i] = -1;
	for(int i = 0; i < sz(genap); i++){
		for(int j = 0; j < sz(ganjil); j++)
			sudah[j] = false;
		ret += dfs(i);
	}
	return ret;
}

int main(){
	p[1] = true;
	for(int i = 2; i <= 1e7 + 1; i++){
		if(p[i])
			continue;
		if(i > 2)
			prima.pb(i);
		for(int j = i + i; j <= 1e7 + 1; j += i)
			p[j] = true;
	}
	int n;
	cin >> n;	
	for(int i = 0; i < n; i++){
		int x;
		cin >> x;
		ya[x] = true;
	}
	for(int i = 1; i <= 1e7 + 1; i++){
		if(ya[i] ^ ya[i - 1]){
			if(i % 2 == 0)
				genap.pb(i);
			else ganjil.pb(i);
		}
	}
	// debug(sz(genap));
	// debug(sz(ganjil));
	// for(int i : genap)
	// 	debug(i);
	// for(int i : ganjil)
	// 	debug(i);
	int aa = match();
	int sisaGenap = sz(genap) - aa;
	int sisaGanjil = sz(ganjil) - aa;
	int jaw = aa + (sisaGenap / 2) * 2 + (sisaGanjil / 2) * 2;
	if(sisaGanjil % 2 > 0){
		assert(sisaGenap % 2 > 0);
		jaw += 3;
	}
	cout << jaw << endl;
}
```