#include<bits/stdc++.h>
using namespace std;
long long read()
{
	char ch=getchar();long long x=0,ff=1;
	while(ch<'0'||ch>'9') {if(ch=='-') ff=-ff;ch=getchar();}
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return x*ff;
}
void write(long long aa)
{
	if(aa<0) putchar('-'),aa=-aa;
	if(aa>9) write(aa/10);
	putchar(aa%10+'0');
	return;
}
long long n,cnt,L,R,ans;
long long a[105],md[205];
long long l[205],r[205],no[205],yes[205],vis[205];
long long tot,head[205],nx[400005],to[400005];
void add(long long aa,long long bb)
{
	tot++;
	nx[tot]=head[aa];
	to[tot]=bb;
	head[aa]=tot;
	return;
}
long long ok(long long aa,long long bb)
{
	long long len=abs(md[aa]-md[bb]);if(len==1) return 0;
	for(long long i=2;i*i<=len;++i) if(len%i==0) return 0;
	return 1;
}
long long dfs(long long rt)
{
	for(long long i=head[rt];i;i=nx[i])
	{
		long long yy=to[i];
		if(vis[yy]) continue;vis[yy]=1;
		if(!no[yy]||dfs(no[yy])) {no[yy]=rt;yes[rt]=yy;return 1;}
	}
	return 0;
}
int main()
{
	n=read();a[0]=-10;
	for(long long i=1;i<=n;++i) a[i]=read();
	for(long long i=1;i<=n;++i) 
	{
		if(a[i]!=a[i-1]+1) md[++cnt]=a[i]-1;
		if(a[i]+1!=a[i+1]) md[++cnt]=a[i];
	}
	for(long long i=1;i<=cnt;++i) 
	if(md[i]%2==0) l[++L]=i;
	else r[++R]=i;
	for(long long i=1;i<=L;++i) for(long long j=1;j<=R;++j) 
	if(ok(l[i],r[j])) add(l[i],r[j]);//,cout<<l[i]<<" "<<r[j]<<endl;
	for(long long i=1;i<=L;++i) if(!yes[l[i]])
	{
		memset(vis,0,sizeof(vis));
		if(dfs(l[i])) ans++;
	}
	long long ls=L-ans,rs=R-ans;
	ans+=ls/2*2;ans+=rs/2*2;
	if(ls%2==1) ans+=3;
	write(ans);
	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;
long long read()
{
	char ch=getchar();long long x=0,ff=1;
	while(ch<'0'||ch>'9') {if(ch=='-') ff=-ff;ch=getchar();}
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return x*ff;
}
void write(long long aa)
{
	if(aa<0) putchar('-'),aa=-aa;
	if(aa>9) write(aa/10);
	putchar(aa%10+'0');
	return;
}
long long n,cnt,L,R,ans;
long long a[105],md[205];
long long l[205],r[205],no[205],yes[205],vis[205];
long long tot,head[205],nx[400005],to[400005];
void add(long long aa,long long bb)
{
	tot++;
	nx[tot]=head[aa];
	to[tot]=bb;
	head[aa]=tot;
	return;
}
long long ok(long long aa,long long bb)
{
	long long len=abs(md[aa]-md[bb]);if(len==1) return 0;
	for(long long i=2;i*i<=len;++i) if(len%i==0) return 0;
	return 1;
}
long long dfs(long long rt)
{
	for(long long i=head[rt];i;i=nx[i])
	{
		long long yy=to[i];
		if(vis[yy]) continue;vis[yy]=1;
		if(!no[yy]||dfs(no[yy])) {no[yy]=rt;yes[rt]=yy;return 1;}
	}
	return 0;
}
int main()
{
	n=read();a[0]=-10;
	for(long long i=1;i<=n;++i) a[i]=read();
	for(long long i=1;i<=n;++i) 
	{
		if(a[i]!=a[i-1]+1) md[++cnt]=a[i]-1;
		if(a[i]+1!=a[i+1]) md[++cnt]=a[i];
	}
	for(long long i=1;i<=cnt;++i) 
	if(md[i]%2==0) l[++L]=i;
	else r[++R]=i;
	for(long long i=1;i<=L;++i) for(long long j=1;j<=R;++j) 
	if(ok(l[i],r[j])) add(l[i],r[j]);//,cout<<l[i]<<" "<<r[j]<<endl;
	for(long long i=1;i<=L;++i) if(!yes[l[i]])
	{
		memset(vis,0,sizeof(vis));
		if(dfs(l[i])) ans++;
	}
	long long ls=L-ans,rs=R-ans;
	ans+=ls/2*2;ans+=rs/2*2;
	if(ls%2==1) ans+=3;
	write(ans);
	return 0;
}
```