#include <cstdio>
#include <cmath>

#define Rep(i, n) for (int i = 1; i <= n; i ++)

using namespace std;

const int N = 410, N0 = 1e7 + 10;

int d0[N], d[N], cd;

bool isnotprime[N0];
int prime[N0], cnt;
void get_prime()
{
	isnotprime[1] = true;
	for (int i = 2; i <= 1e7 + 5; i ++){
		if (!isnotprime[i]) prime[++ cnt] = i;
		for (int j = 1; j <= cnt && i * prime[j] <= 1e7 + 5; j ++) {
			isnotprime[i * prime[j]] = true;
			if (!(i % prime[j])) break;
		}
	}
}

bool g[N][N], vis[N];
int lnk[N];

bool dfs(int x)
{
	if (vis[x]) return 0;
	vis[x] = true;
	Rep(i, cd) if (g[x][i]){
		if (lnk[i] == -1 || dfs(lnk[i])) {
			lnk[i] = x;
			return true;
		}
	}
	return false;
}

int main()
{
	int n;
	scanf("%d", &n);
	Rep(i, n) scanf("%d", &d0[i]);
	d0[0] = -1;
	Rep(i, n) {
		if (d0[i - 1] != d0[i] - 1) d[++ cd] = d0[i];
		if (d0[i + 1] != d0[i] + 1) d[++ cd] = d0[i] + 1;
	}
	
	get_prime();
	Rep(i, cd) if (d[i] & 1)
		Rep(j, cd) if (!(d[j] & 1))
			if (!isnotprime[(int)abs(d[j] - d[i])]) g[i][j] = true;
	
	int c0 = 0, c1 = 0, cc = 0;
	Rep(i, cd) lnk[i] = -1;
	Rep(i, cd) {
		if (d[i] & 1) {
			Rep(j, cd) vis[j] = false;
			if (dfs(i)) cc ++;
			c1 ++;
		}
		else c0 ++;
	}
	int ans = cc;
	c0 -= cc, c1 -= cc;
	ans += (c0 / 2) * 2, c0 %= 2;
	ans += (c1 / 2) * 2, c1 %= 2;
	if (c0 && c1) ans += 3;
	
	printf("%d\n", ans);
	
	return 0;
}
### 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 <cmath>

#define Rep(i, n) for (int i = 1; i <= n; i ++)

using namespace std;

const int N = 410, N0 = 1e7 + 10;

int d0[N], d[N], cd;

bool isnotprime[N0];
int prime[N0], cnt;
void get_prime()
{
	isnotprime[1] = true;
	for (int i = 2; i <= 1e7 + 5; i ++){
		if (!isnotprime[i]) prime[++ cnt] = i;
		for (int j = 1; j <= cnt && i * prime[j] <= 1e7 + 5; j ++) {
			isnotprime[i * prime[j]] = true;
			if (!(i % prime[j])) break;
		}
	}
}

bool g[N][N], vis[N];
int lnk[N];

bool dfs(int x)
{
	if (vis[x]) return 0;
	vis[x] = true;
	Rep(i, cd) if (g[x][i]){
		if (lnk[i] == -1 || dfs(lnk[i])) {
			lnk[i] = x;
			return true;
		}
	}
	return false;
}

int main()
{
	int n;
	scanf("%d", &n);
	Rep(i, n) scanf("%d", &d0[i]);
	d0[0] = -1;
	Rep(i, n) {
		if (d0[i - 1] != d0[i] - 1) d[++ cd] = d0[i];
		if (d0[i + 1] != d0[i] + 1) d[++ cd] = d0[i] + 1;
	}
	
	get_prime();
	Rep(i, cd) if (d[i] & 1)
		Rep(j, cd) if (!(d[j] & 1))
			if (!isnotprime[(int)abs(d[j] - d[i])]) g[i][j] = true;
	
	int c0 = 0, c1 = 0, cc = 0;
	Rep(i, cd) lnk[i] = -1;
	Rep(i, cd) {
		if (d[i] & 1) {
			Rep(j, cd) vis[j] = false;
			if (dfs(i)) cc ++;
			c1 ++;
		}
		else c0 ++;
	}
	int ans = cc;
	c0 -= cc, c1 -= cc;
	ans += (c0 / 2) * 2, c0 %= 2;
	ans += (c1 / 2) * 2, c1 %= 2;
	if (c0 && c1) ans += 3;
	
	printf("%d\n", ans);
	
	return 0;
}
```