#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int maxn=210;
int n,k,pri[10000010],linker[maxn],a[maxn],b[maxn];
bool mark[10000010],vis[maxn];
vector<int> v[maxn];
void pre()
{
	n=10000000;
	mark[1]=true;
	for (int i=2;i<=n;i++)
	{
		if (!mark[i])
		{
			pri[k++]=i;
			//cerr<<i<<endl;
		}
		for (int j=0;j<k;j++)
		{
			int m=i*pri[j];
			if (m>n)
			{
				break;
			}
			mark[m]=true;
			if (i%pri[j]==0)
			{
				break;
			}
		}
	}
}
bool dfs(int x)
{
	for (int i=0;i<v[x].size();i++)
	{
		int y=v[x][i];
		if (vis[y])
		{
			continue;
		}
		vis[y]=true;
		if (linker[y]==-1 || dfs(linker[y]))
		{
			linker[y]=x;
			return true;
		}
	}
	return false;
}
int main()
{
	pre();
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	int k=0;
	b[++k]=a[1]-1;
	for (int i=2;i<=n;i++)
	{
		if (a[i]!=a[i-1]+1)
		{
			b[++k]=a[i-1];
			b[++k]=a[i]-1;
		}
	}
	b[++k]=a[n];
	n=k;
	/*
	if (n>200)
	{
		return 0;
	}
	*/
	for (int i=1;i<=n;i++)
	{
		linker[i]=-1;
		//cerr<<b[i]<<endl;
		for (int j=i+1;j<=n;j++)
		{
			/*
			if (abs(b[i]-b[j])>10000000)
			{
				return 0;
			}
			*/
			if ((b[i]+b[j])&1 && !mark[abs(b[i]-b[j])])
			{
				//cerr<<i<<" "<<j<<" "<<abs(b[i]-b[j])<<" "<<mark[9]<<endl;
				if (b[i]&1)
				{
					v[i].pb(j);
				}
				else
				{
					v[j].pb(i);
				}
			}
		}
	}
	int s=0;
	for (int i=1;i<=n;i++)
	{
		if (!(b[i]&1))
		{
			continue;
		}
		memset(vis,false,sizeof(vis));
		if (dfs(i))
		{
			s++;
		}
	}
	int s1=0,s2=0;
	for (int i=1;i<=n;i++)
	{
		if (b[i]&1)
		{
			s1++;
		}
		else
		{
			s2++;
		}
	}
	int ans=s+((s1-s)/2+(s2-s)/2)*2+((s1-s)&1)*3;
	cout<<ans<<endl;
	return 0;
}

### Prompt

Your challenge is to write 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;
#define pb push_back
const int maxn=210;
int n,k,pri[10000010],linker[maxn],a[maxn],b[maxn];
bool mark[10000010],vis[maxn];
vector<int> v[maxn];
void pre()
{
	n=10000000;
	mark[1]=true;
	for (int i=2;i<=n;i++)
	{
		if (!mark[i])
		{
			pri[k++]=i;
			//cerr<<i<<endl;
		}
		for (int j=0;j<k;j++)
		{
			int m=i*pri[j];
			if (m>n)
			{
				break;
			}
			mark[m]=true;
			if (i%pri[j]==0)
			{
				break;
			}
		}
	}
}
bool dfs(int x)
{
	for (int i=0;i<v[x].size();i++)
	{
		int y=v[x][i];
		if (vis[y])
		{
			continue;
		}
		vis[y]=true;
		if (linker[y]==-1 || dfs(linker[y]))
		{
			linker[y]=x;
			return true;
		}
	}
	return false;
}
int main()
{
	pre();
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	int k=0;
	b[++k]=a[1]-1;
	for (int i=2;i<=n;i++)
	{
		if (a[i]!=a[i-1]+1)
		{
			b[++k]=a[i-1];
			b[++k]=a[i]-1;
		}
	}
	b[++k]=a[n];
	n=k;
	/*
	if (n>200)
	{
		return 0;
	}
	*/
	for (int i=1;i<=n;i++)
	{
		linker[i]=-1;
		//cerr<<b[i]<<endl;
		for (int j=i+1;j<=n;j++)
		{
			/*
			if (abs(b[i]-b[j])>10000000)
			{
				return 0;
			}
			*/
			if ((b[i]+b[j])&1 && !mark[abs(b[i]-b[j])])
			{
				//cerr<<i<<" "<<j<<" "<<abs(b[i]-b[j])<<" "<<mark[9]<<endl;
				if (b[i]&1)
				{
					v[i].pb(j);
				}
				else
				{
					v[j].pb(i);
				}
			}
		}
	}
	int s=0;
	for (int i=1;i<=n;i++)
	{
		if (!(b[i]&1))
		{
			continue;
		}
		memset(vis,false,sizeof(vis));
		if (dfs(i))
		{
			s++;
		}
	}
	int s1=0,s2=0;
	for (int i=1;i<=n;i++)
	{
		if (b[i]&1)
		{
			s1++;
		}
		else
		{
			s2++;
		}
	}
	int ans=s+((s1-s)/2+(s2-s)/2)*2+((s1-s)&1)*3;
	cout<<ans<<endl;
	return 0;
}

```