#include <bits/stdc++.h>

#define For(i, j, k) for(int i = j; i <= k; i++)
#define pb push_back

using namespace std;

const int N = 210;
const int M = 1e7 + 10;

bool vis[M];
int prm[M], tot;

void init(int n){
	vis[1] = true;
	For(i, 2, n){
		if(!vis[i]) prm[++tot] = i;
		for(int j = 1; j <= tot && prm[j] * i <= n; ++j){
			vis[prm[j] * i] = true;
			if(i % prm[j] == 0) break;
		}
	}
}

int n, m;
vector<int> G[N];
int pos[N], match[N], used[N];

bool Hungary(int o){
	if(used[o]) return false;
	used[o] = true;
	for(int v : G[o]){
		int &x = match[v];
		if(!x || Hungary(x)){
			x = o;
			return true;
		}
	}
	return false;
}

int main(){
	
	init(M - 5);
	scanf("%d", &n);
	For(i, 1, n){
		int x;
		scanf("%d", &x);
		pos[++m] = x, pos[++m] = x + 1;
	}

	sort(pos + 1, pos + m + 1);
	int node = 0;
	For(i, 1, m){
		if(pos[i + 1] == pos[i]) ++i;
		else pos[++node] = pos[i];
	}
	For(i, 1, node) if(pos[i] & 1)
		For(j, 1, node){
			int x = abs(pos[i] - pos[j]);
			if(pos[j] % 2 == 0 && !vis[x]){
				G[i].pb(j);
			}
		}

	int ret = 0, odd = 0;
	For(i, 1, node) if(pos[i] & 1){
		++odd;
		memset(used, false, sizeof used);
		ret += Hungary(i);
	}

	int even = node - odd - ret;
	odd -= ret;
	if(even & 1) ret = node - ret + 1;
	else ret = node - ret;

	printf("%d\n", ret);

	return 0;
}
### Prompt

Please provide a CPP coded solution to the problem described below:

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>

#define For(i, j, k) for(int i = j; i <= k; i++)
#define pb push_back

using namespace std;

const int N = 210;
const int M = 1e7 + 10;

bool vis[M];
int prm[M], tot;

void init(int n){
	vis[1] = true;
	For(i, 2, n){
		if(!vis[i]) prm[++tot] = i;
		for(int j = 1; j <= tot && prm[j] * i <= n; ++j){
			vis[prm[j] * i] = true;
			if(i % prm[j] == 0) break;
		}
	}
}

int n, m;
vector<int> G[N];
int pos[N], match[N], used[N];

bool Hungary(int o){
	if(used[o]) return false;
	used[o] = true;
	for(int v : G[o]){
		int &x = match[v];
		if(!x || Hungary(x)){
			x = o;
			return true;
		}
	}
	return false;
}

int main(){
	
	init(M - 5);
	scanf("%d", &n);
	For(i, 1, n){
		int x;
		scanf("%d", &x);
		pos[++m] = x, pos[++m] = x + 1;
	}

	sort(pos + 1, pos + m + 1);
	int node = 0;
	For(i, 1, m){
		if(pos[i + 1] == pos[i]) ++i;
		else pos[++node] = pos[i];
	}
	For(i, 1, node) if(pos[i] & 1)
		For(j, 1, node){
			int x = abs(pos[i] - pos[j]);
			if(pos[j] % 2 == 0 && !vis[x]){
				G[i].pb(j);
			}
		}

	int ret = 0, odd = 0;
	For(i, 1, node) if(pos[i] & 1){
		++odd;
		memset(used, false, sizeof used);
		ret += Hungary(i);
	}

	int even = node - odd - ret;
	odd -= ret;
	if(even & 1) ret = node - ret + 1;
	else ret = node - ret;

	printf("%d\n", ret);

	return 0;
}
```