#include <bits/stdc++.h>

const int N = 205, M = 10000005;
int tot = 0, s[N];

bool prime(int n) {
	if (n <= 2) return 0;
	for (int i = 2; i * i <= n; ++i)
		if (n % i == 0) return 0;
	return 1;
}
bool e[N][N];

std::vector<int> L, R;
int l, r, bel[N], match; bool vis[N];

bool dfs(int x) {
	for (int i = 0; i < r; ++i) if (e[x][i] && !vis[i]) {
		vis[i] = 1;
		if (!~bel[i] || dfs(bel[i])) {
			bel[i] = x; return 1;
		}
	}
	return 0;
}

int main() {
	std::ios::sync_with_stdio(0), std::cin.tie(0);
	int n; std::cin >> n;
	for (int i = 0; i < n; ++i) {
		int x; std::cin >> x;
		if (s[tot] == x) --tot;
		else s[++tot] = x;
		s[++tot] = x + 1;
	}
	for (int i = 1; i <= tot; ++i)
		(s[i] & 1 ? L : R).emplace_back(s[i]);
	l = L.size(), r = R.size(), std::memset(bel, -1, sizeof bel);
	for (int i = 0; i < l; ++i)
		for (int j = 0; j < r; ++j)
			e[i][j] = prime(std::abs(L[i] - R[j]));
	for (int i = 0; i < l; ++i) std::memset(vis, 0, r), match += dfs(i);
	std::cout << l + r - match + (l - match & 1) << '\n';
	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 <bits/stdc++.h>

const int N = 205, M = 10000005;
int tot = 0, s[N];

bool prime(int n) {
	if (n <= 2) return 0;
	for (int i = 2; i * i <= n; ++i)
		if (n % i == 0) return 0;
	return 1;
}
bool e[N][N];

std::vector<int> L, R;
int l, r, bel[N], match; bool vis[N];

bool dfs(int x) {
	for (int i = 0; i < r; ++i) if (e[x][i] && !vis[i]) {
		vis[i] = 1;
		if (!~bel[i] || dfs(bel[i])) {
			bel[i] = x; return 1;
		}
	}
	return 0;
}

int main() {
	std::ios::sync_with_stdio(0), std::cin.tie(0);
	int n; std::cin >> n;
	for (int i = 0; i < n; ++i) {
		int x; std::cin >> x;
		if (s[tot] == x) --tot;
		else s[++tot] = x;
		s[++tot] = x + 1;
	}
	for (int i = 1; i <= tot; ++i)
		(s[i] & 1 ? L : R).emplace_back(s[i]);
	l = L.size(), r = R.size(), std::memset(bel, -1, sizeof bel);
	for (int i = 0; i < l; ++i)
		for (int j = 0; j < r; ++j)
			e[i][j] = prime(std::abs(L[i] - R[j]));
	for (int i = 0; i < l; ++i) std::memset(vis, 0, r), match += dfs(i);
	std::cout << l + r - match + (l - match & 1) << '\n';
	return 0;
}
```