#include<bits/stdc++.h>
using namespace std;
const int N=105;
const int L=10000005;
int n;
int a[L],b[L];
int totc,c[N<<1];
bool isprime(int x)
{
	if(x==1) return 0;//
	int m=int(sqrt(x));
	for(int i=2;i<=m;i++)
		if(x%i==0) return 0;
	return 1;
}
int val1[N<<1],cnt1,val2[N<<1],cnt2;
int sum,h[N<<1];
struct Edge{int v,nxt;}e[2*N*2*N];
void adde(int x,int y){sum++;e[sum].v=y;e[sum].nxt=h[x];h[x]=sum;}
bool v[N<<2];
int match[N<<2];
bool dfs(int x)
{
	for(int i=h[x];i;i=e[i].nxt)
	{
		int y=e[i].v;
		if(v[y]) continue;
		v[y]=1;
		if(!match[y]||dfs(match[y]))
		{
			match[y]=x;
			return 1;
		}
	}
	return 0;
}
int main()
{
	scanf("%d",&n);
	int mx=0;
	for(int i=1;i<=n;i++)
	{
		int x;
		scanf("%d",&x);
		a[x]=1;
		mx=max(mx,x);
	}
	if(a[1]==1) b[1]=1,c[++totc]=1;
	for(int i=2;i<=mx+1;i++)//for(int i=2;i<=mx;i++)
	{
		b[i]=a[i-1]^a[i];
		if(b[i]) c[++totc]=i;
	}
	//for(int i=1;i<=totc;i++) printf("%d ",c[i]);printf("\n");
	for(int i=1;i<=totc;i++)
	{
		if(c[i]&1) val1[++cnt1]=c[i];//if(c[i]&1) val1[++cnt1]=i;
		else val2[++cnt2]=c[i];//else val2[++cnt2]=i;
	}
	//for(int i=1;i<=cnt1;i++) printf("%d ",val1[i]);printf("\n");
	//for(int i=1;i<=cnt2;i++) printf("%d ",val2[i]);printf("\n");
	for(int i=1;i<=cnt1;i++)
		for(int j=1;j<=cnt2;j++)
			if(isprime(abs(val2[j]-val1[i])))//if(isprime(val2[j]-val1[i]))
				adde(i,200+j);
	int matched=0;
	for(int i=1;i<=cnt1;i++)
	{
		memset(v,0,sizeof(v));
		if(dfs(i)) matched++;
	}
	//printf("%d %d %d\n",cnt1,cnt2,matched);
	int ans=matched;
	ans+=(cnt1-matched)/2*2;
	//ans+=((cnt1-matched)&1)*3;
	ans+=(cnt2-matched)/2*2;
	//ans+=((cnt2-matched)&1)*3;
	if(((cnt1-matched)&1)&&((cnt2-matched)&1)) ans+=3;
	else if(((cnt1-matched)&1)||((cnt2-matched)&1)) ans+=3;
	printf("%d\n",ans);
	return 0;
}
### Prompt

Construct a cpp code solution to the problem outlined:

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;
const int N=105;
const int L=10000005;
int n;
int a[L],b[L];
int totc,c[N<<1];
bool isprime(int x)
{
	if(x==1) return 0;//
	int m=int(sqrt(x));
	for(int i=2;i<=m;i++)
		if(x%i==0) return 0;
	return 1;
}
int val1[N<<1],cnt1,val2[N<<1],cnt2;
int sum,h[N<<1];
struct Edge{int v,nxt;}e[2*N*2*N];
void adde(int x,int y){sum++;e[sum].v=y;e[sum].nxt=h[x];h[x]=sum;}
bool v[N<<2];
int match[N<<2];
bool dfs(int x)
{
	for(int i=h[x];i;i=e[i].nxt)
	{
		int y=e[i].v;
		if(v[y]) continue;
		v[y]=1;
		if(!match[y]||dfs(match[y]))
		{
			match[y]=x;
			return 1;
		}
	}
	return 0;
}
int main()
{
	scanf("%d",&n);
	int mx=0;
	for(int i=1;i<=n;i++)
	{
		int x;
		scanf("%d",&x);
		a[x]=1;
		mx=max(mx,x);
	}
	if(a[1]==1) b[1]=1,c[++totc]=1;
	for(int i=2;i<=mx+1;i++)//for(int i=2;i<=mx;i++)
	{
		b[i]=a[i-1]^a[i];
		if(b[i]) c[++totc]=i;
	}
	//for(int i=1;i<=totc;i++) printf("%d ",c[i]);printf("\n");
	for(int i=1;i<=totc;i++)
	{
		if(c[i]&1) val1[++cnt1]=c[i];//if(c[i]&1) val1[++cnt1]=i;
		else val2[++cnt2]=c[i];//else val2[++cnt2]=i;
	}
	//for(int i=1;i<=cnt1;i++) printf("%d ",val1[i]);printf("\n");
	//for(int i=1;i<=cnt2;i++) printf("%d ",val2[i]);printf("\n");
	for(int i=1;i<=cnt1;i++)
		for(int j=1;j<=cnt2;j++)
			if(isprime(abs(val2[j]-val1[i])))//if(isprime(val2[j]-val1[i]))
				adde(i,200+j);
	int matched=0;
	for(int i=1;i<=cnt1;i++)
	{
		memset(v,0,sizeof(v));
		if(dfs(i)) matched++;
	}
	//printf("%d %d %d\n",cnt1,cnt2,matched);
	int ans=matched;
	ans+=(cnt1-matched)/2*2;
	//ans+=((cnt1-matched)&1)*3;
	ans+=(cnt2-matched)/2*2;
	//ans+=((cnt2-matched)&1)*3;
	if(((cnt1-matched)&1)&&((cnt2-matched)&1)) ans+=3;
	else if(((cnt1-matched)&1)||((cnt2-matched)&1)) ans+=3;
	printf("%d\n",ans);
	return 0;
}
```