#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
const int N = 205;
const int M = 1e7 + 5; 
using namespace std;

int lim = 10000001, n, path[N][N], l[N], r[N], cntl, cntr, vis[M], bl[N], prm[M], top, s[M]; 

template < typename T >
inline T read()
{
	T x = 0, w = 1; char c = getchar();
	while(c < '0' || c > '9') { if(c == '-') w = -1; c = getchar(); }
	while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return x * w; 
}

bool dfs(int u)
{
	for(int i = 1; i <= cntr; i++)
		if(!vis[i] && path[u][i])
		{
			vis[i] = 1; 
			if(!bl[i] || dfs(bl[i]))
			{
				bl[i] = u; return 1; 
			}
		}
	return 0; 
}

int hungary()
{
	int cnt = 0;
	for(int i = 1; i <= cntl; i++)
	{
		for(int j = 1; j <= max(cntl, cntr); j++) vis[j] = 0; 
		if(dfs(i)) cnt++; 
	}
	return cnt; 
}

void Euler()
{
	vis[1] = 1; 
	for(int i = 2; i <= lim; i++)
	{
		if(!vis[i]) prm[++top] = i;
		for(int j = 1; i * prm[j] <= lim; j++)
		{
			vis[i * prm[j]] = 1; 
			if(i % prm[j] == 0) break; 
		}
	}
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("cpp.in", "r", stdin); 
#endif
	Euler();
	n = read <int> ();
	for(int x, i = 1; i <= n; i++) x = read <int> (), s[x] = 1;
	for(int i = 1; i <= lim; i++)
		if(s[i] != s[i - 1])
		{
			if(i & 1) l[++cntl] = i; 
			else r[++cntr] = i; 
		}
	for(int i = 1; i <= cntl; i++)
		for(int j = 1; j <= cntr; j++)
			if(!vis[l[i] - r[j] > 0 ? l[i] - r[j] : r[j] - l[i]])
				path[i][j] = 1; 
	int tmp = hungary(), ans = tmp;
	cntl -= tmp, cntr -= tmp, ans += cntl / 2 * 2, cntl %= 2, ans += cntr / 2 * 2, cntr %= 2;
	if(cntl && cntr) ans += 3;
	printf("%d\n", ans); 
	return 0; 
}

### Prompt

Your task is to create 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 <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
const int N = 205;
const int M = 1e7 + 5; 
using namespace std;

int lim = 10000001, n, path[N][N], l[N], r[N], cntl, cntr, vis[M], bl[N], prm[M], top, s[M]; 

template < typename T >
inline T read()
{
	T x = 0, w = 1; char c = getchar();
	while(c < '0' || c > '9') { if(c == '-') w = -1; c = getchar(); }
	while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return x * w; 
}

bool dfs(int u)
{
	for(int i = 1; i <= cntr; i++)
		if(!vis[i] && path[u][i])
		{
			vis[i] = 1; 
			if(!bl[i] || dfs(bl[i]))
			{
				bl[i] = u; return 1; 
			}
		}
	return 0; 
}

int hungary()
{
	int cnt = 0;
	for(int i = 1; i <= cntl; i++)
	{
		for(int j = 1; j <= max(cntl, cntr); j++) vis[j] = 0; 
		if(dfs(i)) cnt++; 
	}
	return cnt; 
}

void Euler()
{
	vis[1] = 1; 
	for(int i = 2; i <= lim; i++)
	{
		if(!vis[i]) prm[++top] = i;
		for(int j = 1; i * prm[j] <= lim; j++)
		{
			vis[i * prm[j]] = 1; 
			if(i % prm[j] == 0) break; 
		}
	}
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("cpp.in", "r", stdin); 
#endif
	Euler();
	n = read <int> ();
	for(int x, i = 1; i <= n; i++) x = read <int> (), s[x] = 1;
	for(int i = 1; i <= lim; i++)
		if(s[i] != s[i - 1])
		{
			if(i & 1) l[++cntl] = i; 
			else r[++cntr] = i; 
		}
	for(int i = 1; i <= cntl; i++)
		for(int j = 1; j <= cntr; j++)
			if(!vis[l[i] - r[j] > 0 ? l[i] - r[j] : r[j] - l[i]])
				path[i][j] = 1; 
	int tmp = hungary(), ans = tmp;
	cntl -= tmp, cntr -= tmp, ans += cntl / 2 * 2, cntl %= 2, ans += cntr / 2 * 2, cntr %= 2;
	if(cntl && cntr) ans += 3;
	printf("%d\n", ans); 
	return 0; 
}

```