#include <cstdio>
#include <vector>
#include <cstring>
const int maxP = 1e7;
const int maxn = 205;
const int S = 0;
const int T = 204;
using namespace std;
vector <int> p; bool isp[maxP + 5];
void install(){
	isp[1] = 1;
	for (int i = 2; i <= maxP; i++){
		if (!isp[i]) p.push_back(i);
		for (int j = 0; j < p.size() && i * p[j] <= maxP; j++){
			isp[i * p[j]] = 1;
			if (i % p[j] == 0) break;
		}
	}
}
struct E{
	int to, nxt;
}e[maxn * maxn];
int head[maxn], tot = 1;
void addedge(int u, int v){
	e[++tot].to = v, e[tot].nxt = head[u];
	head[u] = tot;
}
int mat[maxn]; bool vis[maxn];
bool dfs(int cur){ 
	for (int i = head[cur]; i; i = e[i].nxt){
		int v = e[i].to;
		if (vis[v]) continue;
		vis[v] = 1;
		if (mat[v] == -1 || dfs(mat[v])){
			mat[v] = cur; mat[cur] = v;
			return true;
		}
	}
	return false;
}
int abs(int x){return x < 0 ? -x : x;}
vector <int> x[2]; int n, c[maxP + 5];
int main(){
	install();
	scanf("%d", &n);
	for (int a, i = 1; i <= n; i++){
		scanf("%d", &a); c[a]++;
	}
	for (int i = 1; i <= maxP + 1; i++)
		if (c[i] != c[i - 1]) x[i & 1].push_back(i);
	for (int i = 0; i < x[0].size(); i++)
		for (int j = 0; j < x[1].size(); j++)
			if (!isp[abs(x[1][j] - x[0][i])]) addedge(i, j + x[0].size());
	int flow = 0;
	memset(mat, -1, sizeof mat);
	for (int i = 0; i < x[0].size() + x[1].size(); i++){
		if (mat[i] == -1){
			memset(vis, 0, sizeof vis);
			flow += dfs(i);
		}
	}
	printf("%d\n", flow + (x[0].size() - flow) / 2 * 2 + (x[1].size() - flow) / 2 * 2 + (x[0].size() - flow) % 2 * 3);
	return 0;
}
### 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 <cstdio>
#include <vector>
#include <cstring>
const int maxP = 1e7;
const int maxn = 205;
const int S = 0;
const int T = 204;
using namespace std;
vector <int> p; bool isp[maxP + 5];
void install(){
	isp[1] = 1;
	for (int i = 2; i <= maxP; i++){
		if (!isp[i]) p.push_back(i);
		for (int j = 0; j < p.size() && i * p[j] <= maxP; j++){
			isp[i * p[j]] = 1;
			if (i % p[j] == 0) break;
		}
	}
}
struct E{
	int to, nxt;
}e[maxn * maxn];
int head[maxn], tot = 1;
void addedge(int u, int v){
	e[++tot].to = v, e[tot].nxt = head[u];
	head[u] = tot;
}
int mat[maxn]; bool vis[maxn];
bool dfs(int cur){ 
	for (int i = head[cur]; i; i = e[i].nxt){
		int v = e[i].to;
		if (vis[v]) continue;
		vis[v] = 1;
		if (mat[v] == -1 || dfs(mat[v])){
			mat[v] = cur; mat[cur] = v;
			return true;
		}
	}
	return false;
}
int abs(int x){return x < 0 ? -x : x;}
vector <int> x[2]; int n, c[maxP + 5];
int main(){
	install();
	scanf("%d", &n);
	for (int a, i = 1; i <= n; i++){
		scanf("%d", &a); c[a]++;
	}
	for (int i = 1; i <= maxP + 1; i++)
		if (c[i] != c[i - 1]) x[i & 1].push_back(i);
	for (int i = 0; i < x[0].size(); i++)
		for (int j = 0; j < x[1].size(); j++)
			if (!isp[abs(x[1][j] - x[0][i])]) addedge(i, j + x[0].size());
	int flow = 0;
	memset(mat, -1, sizeof mat);
	for (int i = 0; i < x[0].size() + x[1].size(); i++){
		if (mat[i] == -1){
			memset(vis, 0, sizeof vis);
			flow += dfs(i);
		}
	}
	printf("%d\n", flow + (x[0].size() - flow) / 2 * 2 + (x[1].size() - flow) / 2 * 2 + (x[0].size() - flow) % 2 * 3);
	return 0;
}
```