#include <cstdio>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fod(i,a,b) for(int i=a;i>=b;--i)
#define min(q,w) ((q)>(w)?(w):(q))
#define max(q,w) ((q)<(w)?(w):(q))
using namespace std;
const int N=350,M=1e7;
int read(int &n)
{
	char ch=' ';int q=0,w=1;
	for(;(ch!='-')&&((ch<'0')||(ch>'9'));ch=getchar());
	if(ch=='-')w=-1,ch=getchar();
	for(;ch>='0' && ch<='9';ch=getchar())q=q*10+ch-48;n=q*w;return n;
}
int m,n,ans;
bool az[M+10],prz[M+10];
bool B[N][N];
int pr[M/5];
int a[N],b[N],zx[N];
int z[N],TI;
void Pre()
{
	fo(i,2,M)
	{
		if(!prz[i])pr[++pr[0]]=i;
		fo(j,1,pr[0])
		{
			int t=i*pr[j];
			if(t>M)break;
			prz[t]=1;
			if(!t%pr[j])break;
		}
	}
	prz[1]=prz[2]=1;
}
bool OK(int q)
{
	if(z[q]==TI)return 0;
	z[q]=TI;
	fo(i,1,b[0])if(B[q][i]&&(!zx[i]||OK(zx[i])))return zx[i]=q,1;
	return 0;
}
int main()
{
	int q;
	Pre();
	read(n);
	fo(i,1,n)az[read(q)]=1;
	fo(i,1,M+1)if(az[i]!=az[i-1])
	{
		if(i&1)a[++a[0]]=i;
		else b[++b[0]]=i;
	}
	fo(i,1,a[0])fo(j,1,b[0])if(!prz[abs(a[i]-b[j])])B[i][j]=1;
	q=0;
	fo(i,1,a[0])
	{
		++TI;if(OK(i))++q;
	}
	ans=q+2*((a[0]-q)/2+(b[0]-q)/2);
	if((a[0]-q)&1)ans+=3;
	printf("%d\n",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 <cstdio>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fod(i,a,b) for(int i=a;i>=b;--i)
#define min(q,w) ((q)>(w)?(w):(q))
#define max(q,w) ((q)<(w)?(w):(q))
using namespace std;
const int N=350,M=1e7;
int read(int &n)
{
	char ch=' ';int q=0,w=1;
	for(;(ch!='-')&&((ch<'0')||(ch>'9'));ch=getchar());
	if(ch=='-')w=-1,ch=getchar();
	for(;ch>='0' && ch<='9';ch=getchar())q=q*10+ch-48;n=q*w;return n;
}
int m,n,ans;
bool az[M+10],prz[M+10];
bool B[N][N];
int pr[M/5];
int a[N],b[N],zx[N];
int z[N],TI;
void Pre()
{
	fo(i,2,M)
	{
		if(!prz[i])pr[++pr[0]]=i;
		fo(j,1,pr[0])
		{
			int t=i*pr[j];
			if(t>M)break;
			prz[t]=1;
			if(!t%pr[j])break;
		}
	}
	prz[1]=prz[2]=1;
}
bool OK(int q)
{
	if(z[q]==TI)return 0;
	z[q]=TI;
	fo(i,1,b[0])if(B[q][i]&&(!zx[i]||OK(zx[i])))return zx[i]=q,1;
	return 0;
}
int main()
{
	int q;
	Pre();
	read(n);
	fo(i,1,n)az[read(q)]=1;
	fo(i,1,M+1)if(az[i]!=az[i-1])
	{
		if(i&1)a[++a[0]]=i;
		else b[++b[0]]=i;
	}
	fo(i,1,a[0])fo(j,1,b[0])if(!prz[abs(a[i]-b[j])])B[i][j]=1;
	q=0;
	fo(i,1,a[0])
	{
		++TI;if(OK(i))++q;
	}
	ans=q+2*((a[0]-q)/2+(b[0]-q)/2);
	if((a[0]-q)&1)ans+=3;
	printf("%d\n",ans);
	return 0;
}
```