#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <algorithm>
#define rep(i, a, b) for (int i = (a), _ = (b); i <= _; ++ i)
#define per(i, a, b) for (int i = (a), _ = (b); i >= _; -- i)
#define For(i, a, b) for (int i = (a), _ = (b); i < _; ++ i)
#define ri rd<int>
using namespace std;
const int maxN = 207;
const int M = 10000000;
const int maxM = 1e7 + 7;

template<class T> inline T rd() {
	bool f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = 0;
	T x = 0; for (; isdigit(c); c = getchar()) x = x * 10 + c - 48; return f ? x : -x;
}

int n;
int a[maxN];
int b[maxN], m;
bool ntpri[maxM];
int pri[maxM], cnt;
int link[maxN], vis[maxN];
bool adj[maxN][maxN];

void seive() {
	ntpri[1] = 1;
	rep (i, 2, M) {
		if (!ntpri[i]) pri[++cnt] = i;
		rep (j, 1, cnt) {
			if (1LL * i * pri[j] > M) break;
			ntpri[i * pri[j]] = 1;
			if (i % pri[j] == 0) break;
		}
	}
	ntpri[2] = ntpri[0] = 1;
}

int match(int x) {
	vis[x] = 1;
	rep (y, 1, m) if (adj[x][y] && (!link[y] || (!vis[link[y]] && match(link[y])))) {
		link[y] = x;
		return 1;
	}
	return 0;
}

int main() {

	n = ri();
	rep (i, 1, n) a[i] = ri();

	b[++m] = a[1] - 1;
	rep (i, 2, n) if (a[i-1] + 1 < a[i]) b[++m] = a[i-1], b[++m] = a[i] - 1;
	b[++m] = a[n];

	seive();

	rep (i, 1, m) if (b[i] & 1) 
		rep (j, 1, m) if (ntpri[abs(b[i] - b[j])] == 0) adj[i][j] = 1; 

	int res = 0, cc = 0;
	memset(link, 0, sizeof link);
	rep (i, 1, m) if (b[i] & 1) {
		memset(vis, 0, sizeof vis);
		res += match(i);
		++ cc;
	}

	int ans = res;
	ans += ((cc - res) >> 1) << 1;
	ans += ((m - cc - res) >> 1) << 1;
	ans += 3 * ((m - cc - res) & 1);

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

	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 <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <algorithm>
#define rep(i, a, b) for (int i = (a), _ = (b); i <= _; ++ i)
#define per(i, a, b) for (int i = (a), _ = (b); i >= _; -- i)
#define For(i, a, b) for (int i = (a), _ = (b); i < _; ++ i)
#define ri rd<int>
using namespace std;
const int maxN = 207;
const int M = 10000000;
const int maxM = 1e7 + 7;

template<class T> inline T rd() {
	bool f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = 0;
	T x = 0; for (; isdigit(c); c = getchar()) x = x * 10 + c - 48; return f ? x : -x;
}

int n;
int a[maxN];
int b[maxN], m;
bool ntpri[maxM];
int pri[maxM], cnt;
int link[maxN], vis[maxN];
bool adj[maxN][maxN];

void seive() {
	ntpri[1] = 1;
	rep (i, 2, M) {
		if (!ntpri[i]) pri[++cnt] = i;
		rep (j, 1, cnt) {
			if (1LL * i * pri[j] > M) break;
			ntpri[i * pri[j]] = 1;
			if (i % pri[j] == 0) break;
		}
	}
	ntpri[2] = ntpri[0] = 1;
}

int match(int x) {
	vis[x] = 1;
	rep (y, 1, m) if (adj[x][y] && (!link[y] || (!vis[link[y]] && match(link[y])))) {
		link[y] = x;
		return 1;
	}
	return 0;
}

int main() {

	n = ri();
	rep (i, 1, n) a[i] = ri();

	b[++m] = a[1] - 1;
	rep (i, 2, n) if (a[i-1] + 1 < a[i]) b[++m] = a[i-1], b[++m] = a[i] - 1;
	b[++m] = a[n];

	seive();

	rep (i, 1, m) if (b[i] & 1) 
		rep (j, 1, m) if (ntpri[abs(b[i] - b[j])] == 0) adj[i][j] = 1; 

	int res = 0, cc = 0;
	memset(link, 0, sizeof link);
	rep (i, 1, m) if (b[i] & 1) {
		memset(vis, 0, sizeof vis);
		res += match(i);
		++ cc;
	}

	int ans = res;
	ans += ((cc - res) >> 1) << 1;
	ans += ((m - cc - res) >> 1) << 1;
	ans += 3 * ((m - cc - res) & 1);

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

	return 0;
}

```