#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define per(i, a, b) for (int i = (a); i >= (b); --i)
#define pb push_back
#define mp make_pair
#define pr pair<int, int>
#define x first
#define y second
using namespace std;

template<typename T>
void read(T& n){
	char ch; int sign = 1;
	while (!isdigit(ch = getchar())) if (ch == '-') sign = -1;
	n = ch - '0';
	while (isdigit(ch = getchar())) n = n * 10 + ch - '0';
	n *= sign;
}
typedef long long ll;
const int INF = 1e9 + 7;
const int N = 222;
int n, mx, mark, x;
int cnt[12222222], match[N], vis[N];
vector<int> v[2];
struct edge{int to, nxt;} g[N*N*4];
int ghead[N], gtail(0);

void add(int l, int r){g[++gtail] = (edge){r, ghead[l]}, ghead[l] = gtail;}
bool oddprime(int x){
	rep(i, 2, sqrt(x)) if (x % i == 0) return false;
	return x > 2;
}
bool find(int x){
	vis[x] = mark;
	for (int p = ghead[x]; p; p = g[p].nxt){
		int v = g[p].to; if (vis[match[v]] == mark) continue;
		if (!match[v]||find(match[v])){
			match[v] = x; return true;
		}
	}
	return false;
}

int main(){
	read(n);
	rep(i, 1, n) read(x), cnt[x] = 1, mx = max(mx, x);
	rep(i, 1, mx + 1) if (cnt[i] ^ cnt[i-1]) v[i%2].pb(i);
	int s0 = v[0].size(), s1 = v[1].size();
	rep(i, 1, s0) rep(j, 1, s1)
		if (oddprime(abs(v[0][i-1] - v[1][j-1])))
			add(i, s0 + j);
	int ans = 0;
	rep(i, 1, s0) {mark++; if (find(i)) ans++;}
	printf("%d\n", ans + ((s0 - ans) / 2 + (s1 - ans) / 2) * 2 + (s0 - ans) % 2 * 3);
	return 0;
}
### Prompt

Develop a solution in Cpp 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 rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define per(i, a, b) for (int i = (a); i >= (b); --i)
#define pb push_back
#define mp make_pair
#define pr pair<int, int>
#define x first
#define y second
using namespace std;

template<typename T>
void read(T& n){
	char ch; int sign = 1;
	while (!isdigit(ch = getchar())) if (ch == '-') sign = -1;
	n = ch - '0';
	while (isdigit(ch = getchar())) n = n * 10 + ch - '0';
	n *= sign;
}
typedef long long ll;
const int INF = 1e9 + 7;
const int N = 222;
int n, mx, mark, x;
int cnt[12222222], match[N], vis[N];
vector<int> v[2];
struct edge{int to, nxt;} g[N*N*4];
int ghead[N], gtail(0);

void add(int l, int r){g[++gtail] = (edge){r, ghead[l]}, ghead[l] = gtail;}
bool oddprime(int x){
	rep(i, 2, sqrt(x)) if (x % i == 0) return false;
	return x > 2;
}
bool find(int x){
	vis[x] = mark;
	for (int p = ghead[x]; p; p = g[p].nxt){
		int v = g[p].to; if (vis[match[v]] == mark) continue;
		if (!match[v]||find(match[v])){
			match[v] = x; return true;
		}
	}
	return false;
}

int main(){
	read(n);
	rep(i, 1, n) read(x), cnt[x] = 1, mx = max(mx, x);
	rep(i, 1, mx + 1) if (cnt[i] ^ cnt[i-1]) v[i%2].pb(i);
	int s0 = v[0].size(), s1 = v[1].size();
	rep(i, 1, s0) rep(j, 1, s1)
		if (oddprime(abs(v[0][i-1] - v[1][j-1])))
			add(i, s0 + j);
	int ans = 0;
	rep(i, 1, s0) {mark++; if (find(i)) ans++;}
	printf("%d\n", ans + ((s0 - ans) / 2 + (s1 - ans) / 2) * 2 + (s0 - ans) % 2 * 3);
	return 0;
}
```