#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef vector<int> vi;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define ALL(c) (c).begin(),(c).end()

//bipartite matching
const int MAX_V = 210;

int V; 
vector<int> g[MAX_V];
int match[MAX_V];
bool used[MAX_V];

inline void add_edge(int u, int v)
{
	g[u].push_back(v);
	g[v].push_back(u);
}

bool dfs(int v)
{
	used[v] = true;

	for (int u : g[v]) {
		int w = match[u];
		if (w < 0 || (!used[w] && dfs(w))) {
			match[v] = u;
			match[u] = v;
			return true;
		}
	}

	return false;
}

int bipartite_matching()
{
	int res = 0;
	memset(match, -1, sizeof(match));

	for (int v = 0; v < V; ++v) {
		if (match[v] < 0) {
			memset(used, 0, sizeof(used));
			res += dfs(v);
		}
	}

	return res;
}

const int MX = 10000010;
bool pr[MX];
bool e[MX];

int main() {
	pr[0] = pr[1] = 1;
	for (int i = 2; i < MX; ++i) {
		if (!pr[i]) {
			for (int j = i * 2; j < MX; j += i) {
				pr[j] = 1;
			}
		}
	}

	int N; cin >> N;
	vi x(N);
	rep(i, N) {
		cin >> x[i];
		e[x[i]] = 1;
	}

	vi vx;
	rep(i, MX-1) {
		if (e[i] != e[i+1]) {
			vx.pb(i);
		}
	}

	vi vl, vr;

	V = vx.size();

	rep(i, V) {
		if (vx[i] & 1) {
			vl.pb(vx[i]);
		} else {
			vr.pb(vx[i]);
		}
	}

	rep(i, vl.size()) {
		rep(j, vr.size()) {
			int t = abs(vl[i] - vr[j]);
			if (!pr[t]) {
				add_edge(i, vl.size() + j);
			}
		}
	}

	int t = bipartite_matching();
	int nl = vl.size() - t, nr = vr.size() - t;
	int ans = t;
	int d = nl / 2;
	ans += d * 2;
	nl -= d * 2;
	d = nr / 2;
	ans += d * 2;
	nr -= d * 2;
	ans += 3 * nl;

	cout << ans << endl;


	return 0;
}
### Prompt

Please formulate a CPP solution 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>
using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef vector<int> vi;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define ALL(c) (c).begin(),(c).end()

//bipartite matching
const int MAX_V = 210;

int V; 
vector<int> g[MAX_V];
int match[MAX_V];
bool used[MAX_V];

inline void add_edge(int u, int v)
{
	g[u].push_back(v);
	g[v].push_back(u);
}

bool dfs(int v)
{
	used[v] = true;

	for (int u : g[v]) {
		int w = match[u];
		if (w < 0 || (!used[w] && dfs(w))) {
			match[v] = u;
			match[u] = v;
			return true;
		}
	}

	return false;
}

int bipartite_matching()
{
	int res = 0;
	memset(match, -1, sizeof(match));

	for (int v = 0; v < V; ++v) {
		if (match[v] < 0) {
			memset(used, 0, sizeof(used));
			res += dfs(v);
		}
	}

	return res;
}

const int MX = 10000010;
bool pr[MX];
bool e[MX];

int main() {
	pr[0] = pr[1] = 1;
	for (int i = 2; i < MX; ++i) {
		if (!pr[i]) {
			for (int j = i * 2; j < MX; j += i) {
				pr[j] = 1;
			}
		}
	}

	int N; cin >> N;
	vi x(N);
	rep(i, N) {
		cin >> x[i];
		e[x[i]] = 1;
	}

	vi vx;
	rep(i, MX-1) {
		if (e[i] != e[i+1]) {
			vx.pb(i);
		}
	}

	vi vl, vr;

	V = vx.size();

	rep(i, V) {
		if (vx[i] & 1) {
			vl.pb(vx[i]);
		} else {
			vr.pb(vx[i]);
		}
	}

	rep(i, vl.size()) {
		rep(j, vr.size()) {
			int t = abs(vl[i] - vr[j]);
			if (!pr[t]) {
				add_edge(i, vl.size() + j);
			}
		}
	}

	int t = bipartite_matching();
	int nl = vl.size() - t, nr = vr.size() - t;
	int ans = t;
	int d = nl / 2;
	ans += d * 2;
	nl -= d * 2;
	d = nr / 2;
	ans += d * 2;
	nr -= d * 2;
	ans += 3 * nl;

	cout << ans << endl;


	return 0;
}
```