#include <cstdio>
#include <vector>
#include <string.h>
using namespace std;

#define abs(x) ((x) > 0 ? (x) : -(x))
bool prime[11000000];
bool b[11000000];
int n;
bool used[210], go[210][210];
int ans;
int ind[210];
int cnt0, cnt1;
int m;
int Link[210];

bool fi(int x) {
	for (int i = 1; i <= m; i++)
		if (go[x][i] && !used[i]) {
			used[i] = true;
			if (!Link[i] || fi(Link[i])) {
				Link[i] = x;
				return true;
			}
		}
	return false;
}

int main() {
	scanf("%d", &n);
	for (int i = 2; i <= 10000000; i++)
		prime[i] = true;
	for (int i = 1; i * i <= 10000000; i++)
		if (prime[i])
			for (int j = i * i; j <= 10000000; j += i)
				prime[j] = false;
	prime[2] = false;

	for (int i = 1; i <= n; i++) {
		int t;
		scanf("%d", &t);
		b[t] ^= 1;
		b[t + 1] ^= 1;
	}
	for (int i = 1; i <= 10000001; i++)
		if (b[i]) {
			m += 1;
			ind[m] = i;
		}
	for (int i = 1; i <= m; i++)
		if (ind[i] % 2 == 0) {
			cnt0 += 1;
			for (int j = 1; j <= m; j++)
				if (ind[j] % 2 == 1 && prime[abs(ind[i] - ind[j])])
					go[i][j] = true;
		}
	int ans = 0;
	for (int i = 1; i <= m; i++)
		if (ind[i] % 2 == 0) {
			memset(used, false, sizeof used);
			if (fi(i))
				ans += 1;
		}
	int aa = ans;
	cnt1 = m - cnt0;
	// printf("?? %d %d\n", cnt0, cnt1);
	cnt0 -= ans;
	cnt1 -= ans;
	if (cnt0 % 2 == 0)
		aa += cnt0 + cnt1;
	else
		aa += 3 + (cnt0 - 1) + cnt1 - 1;
	printf("%d\n", aa);
}

### Prompt

Create a solution in cpp for 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 <string.h>
using namespace std;

#define abs(x) ((x) > 0 ? (x) : -(x))
bool prime[11000000];
bool b[11000000];
int n;
bool used[210], go[210][210];
int ans;
int ind[210];
int cnt0, cnt1;
int m;
int Link[210];

bool fi(int x) {
	for (int i = 1; i <= m; i++)
		if (go[x][i] && !used[i]) {
			used[i] = true;
			if (!Link[i] || fi(Link[i])) {
				Link[i] = x;
				return true;
			}
		}
	return false;
}

int main() {
	scanf("%d", &n);
	for (int i = 2; i <= 10000000; i++)
		prime[i] = true;
	for (int i = 1; i * i <= 10000000; i++)
		if (prime[i])
			for (int j = i * i; j <= 10000000; j += i)
				prime[j] = false;
	prime[2] = false;

	for (int i = 1; i <= n; i++) {
		int t;
		scanf("%d", &t);
		b[t] ^= 1;
		b[t + 1] ^= 1;
	}
	for (int i = 1; i <= 10000001; i++)
		if (b[i]) {
			m += 1;
			ind[m] = i;
		}
	for (int i = 1; i <= m; i++)
		if (ind[i] % 2 == 0) {
			cnt0 += 1;
			for (int j = 1; j <= m; j++)
				if (ind[j] % 2 == 1 && prime[abs(ind[i] - ind[j])])
					go[i][j] = true;
		}
	int ans = 0;
	for (int i = 1; i <= m; i++)
		if (ind[i] % 2 == 0) {
			memset(used, false, sizeof used);
			if (fi(i))
				ans += 1;
		}
	int aa = ans;
	cnt1 = m - cnt0;
	// printf("?? %d %d\n", cnt0, cnt1);
	cnt0 -= ans;
	cnt1 -= ans;
	if (cnt0 % 2 == 0)
		aa += cnt0 + cnt1;
	else
		aa += 3 + (cnt0 - 1) + cnt1 - 1;
	printf("%d\n", aa);
}

```