#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=205;
const int inf=10000001;

int n,prime[inf+5],match[N],a[N],b[N],a1,b1,tot;
bool s[inf+5],not_prime[inf+5],vis[N],ma[N][N];

void get_prime(int n)
{
	not_prime[1]=1;
	for (int i=2;i<=n;i++)
	{
		if (!not_prime[i]) prime[++tot]=i;
		for (int j=1;j<=tot&&i*prime[j]<=n;j++)
		{
			not_prime[i*prime[j]]=1;
			if (i%prime[j]==0) break;
		}
	}
}

bool find(int x)
{
	for (int i=1;i<=b1;i++)
		if (ma[x][i]&&!vis[i])
		{
			vis[i]=1;
			if (!match[i]||find(match[i]))
			{
				match[i]=x;
				return 1;
			}
		}
	return 0;
}

int main()
{
	get_prime(inf);
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
		int x;scanf("%d",&x);
		s[x]=1;
	}
	for (int i=1;i<=inf;i++)
		if (s[i]!=s[i-1])
		{
			if (i&1) a[++a1]=i;
			else b[++b1]=i;
		}
	for (int i=1;i<=a1;i++)
		for (int j=1;j<=b1;j++)
			if (!not_prime[abs(a[i]-b[j])]) ma[i][j]=1;
	int ans=0,tmp=0;
	for (int i=1;i<=a1;i++)
	{
		memset(vis,0,sizeof(vis));
		if (find(i)) tmp++,ans++;
	}
	ans+=(a1-tmp)/2*2+(b1-tmp)/2*2;
	if (a1%2!=tmp%2) ans+=3;
	printf("%d",ans);
	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<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=205;
const int inf=10000001;

int n,prime[inf+5],match[N],a[N],b[N],a1,b1,tot;
bool s[inf+5],not_prime[inf+5],vis[N],ma[N][N];

void get_prime(int n)
{
	not_prime[1]=1;
	for (int i=2;i<=n;i++)
	{
		if (!not_prime[i]) prime[++tot]=i;
		for (int j=1;j<=tot&&i*prime[j]<=n;j++)
		{
			not_prime[i*prime[j]]=1;
			if (i%prime[j]==0) break;
		}
	}
}

bool find(int x)
{
	for (int i=1;i<=b1;i++)
		if (ma[x][i]&&!vis[i])
		{
			vis[i]=1;
			if (!match[i]||find(match[i]))
			{
				match[i]=x;
				return 1;
			}
		}
	return 0;
}

int main()
{
	get_prime(inf);
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
		int x;scanf("%d",&x);
		s[x]=1;
	}
	for (int i=1;i<=inf;i++)
		if (s[i]!=s[i-1])
		{
			if (i&1) a[++a1]=i;
			else b[++b1]=i;
		}
	for (int i=1;i<=a1;i++)
		for (int j=1;j<=b1;j++)
			if (!not_prime[abs(a[i]-b[j])]) ma[i][j]=1;
	int ans=0,tmp=0;
	for (int i=1;i<=a1;i++)
	{
		memset(vis,0,sizeof(vis));
		if (find(i)) tmp++,ans++;
	}
	ans+=(a1-tmp)/2*2+(b1-tmp)/2*2;
	if (a1%2!=tmp%2) ans+=3;
	printf("%d",ans);
	return 0;
}
```