#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <set>
#define lowbit(x) (x&(-x))
#define MAX(a,b) (a<b?b:a)
#define MIN(a,b) (a<b?a:b)
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e7;
const int maxn = 3e5 + 5;
ll mod = 1e9 + 7;

int n, vis[N + 5];
vector<int> odd, even, g[205];

int check(int n)
{
	if (n <= 2) return 0;
	int m = sqrt(n);
	for (int i = 2; i <= m; i++) if (n%i == 0) return 0;
	return 1;
}

int link[205], used[205];
int dfs(int u)
{
	for (int j = 0; j < g[u].size(); j++)
	{
		int v = g[u][j];
		if (!used[v])
		{
			used[v] = 1;
			if (link[v] == -1 || dfs(link[v]))
			{
				link[v] = u;
				return 1;
			}
		}
	}
	return 0;
}

int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		int x;
		scanf("%d", &x);
		vis[x] = 1;
	}
	for (int i = 1; i <= N + 1; i++)
	{
		if (vis[i] != vis[i - 1])
		{
			if (i & 1) odd.push_back(i);
			else even.push_back(i);
		}
	}

	int osz = odd.size(), esz = even.size();
	for (int i = 0; i < osz; i++)
	{
		for (int j = 0; j < esz; ++j)
		{
			if (check(abs(odd[i] - even[j])))  g[i].push_back(j);
		}
	}

	memset(link, -1, sizeof(link));
	int k = 0;
	for (int i = 0; i < osz; i++)
	{
		memset(used, 0, sizeof(used));
		k += dfs(i);
	}

	printf("%d", k + ((osz - k) / 2 + (esz - k) / 2) * 2 + ((osz-k) % 2) * 3);
}
### 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 <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <set>
#define lowbit(x) (x&(-x))
#define MAX(a,b) (a<b?b:a)
#define MIN(a,b) (a<b?a:b)
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e7;
const int maxn = 3e5 + 5;
ll mod = 1e9 + 7;

int n, vis[N + 5];
vector<int> odd, even, g[205];

int check(int n)
{
	if (n <= 2) return 0;
	int m = sqrt(n);
	for (int i = 2; i <= m; i++) if (n%i == 0) return 0;
	return 1;
}

int link[205], used[205];
int dfs(int u)
{
	for (int j = 0; j < g[u].size(); j++)
	{
		int v = g[u][j];
		if (!used[v])
		{
			used[v] = 1;
			if (link[v] == -1 || dfs(link[v]))
			{
				link[v] = u;
				return 1;
			}
		}
	}
	return 0;
}

int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		int x;
		scanf("%d", &x);
		vis[x] = 1;
	}
	for (int i = 1; i <= N + 1; i++)
	{
		if (vis[i] != vis[i - 1])
		{
			if (i & 1) odd.push_back(i);
			else even.push_back(i);
		}
	}

	int osz = odd.size(), esz = even.size();
	for (int i = 0; i < osz; i++)
	{
		for (int j = 0; j < esz; ++j)
		{
			if (check(abs(odd[i] - even[j])))  g[i].push_back(j);
		}
	}

	memset(link, -1, sizeof(link));
	int k = 0;
	for (int i = 0; i < osz; i++)
	{
		memset(used, 0, sizeof(used));
		k += dfs(i);
	}

	printf("%d", k + ((osz - k) / 2 + (esz - k) / 2) * 2 + ((osz-k) % 2) * 3);
}
```