#include<bits/stdc++.h>
#define gc getchar()
#define ll long long
#define pb push_back
#define mk make_pair
#define rint register int 
using namespace std;
inline int read(){int w=1,s=0;char ch=getchar();while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}while(isdigit(ch)){s=s*10+ch-'0';ch=getchar();}return  w*s;}
struct node{
	int to,next;
}e[1000010];
int h[1000100],tot;
int X[1000010];
int N;int vis[10000010],prime[1000010],cnt;
int pos1[1000010],num1,pos2[1000010],num2;
int v[660],lk[1010];
inline void add(int from,int to){e[++tot].next=h[from];h[from]=tot;e[tot].to=to;}
inline void Init(int n)
{	vis[1]=1;
	for(rint i=2;i<=n;++i)
	{
		if(!vis[i]) prime[++cnt]=i;
		for(rint j=1;j<=cnt&&prime[j]*i<=n;++j)
		{
			vis[i*prime[j]]=1;
			if(i%prime[j]==0) break;
		}
	}vis[2]=1;
}
unordered_map<int,int> mp;
inline void ADD(int x)
{
	if(x&1) pos1[++num1]=x;
	else    pos2[++num2]=x;
}
inline bool DFS(int now)
{
	for(rint i=h[now];i;i=e[i].next)
	{
		int to=e[i].to;
		if(!v[to])
		{
			v[to]=1;
			if(!lk[to]||DFS(lk[to]))
			{
				lk[to]=now;
				return 1;
			}
		}
	}return 0;
}
int main()
{	N=read();
	for(rint i=1;i<=N;++i) X[i]=read(),mp[X[i]]=1;
	Init(1e7);
	for(rint i=1;i<=N;++i)
	{	
		int las=X[i]-1;
		int nxt=X[i]+1;
		if(mp[las]!=mp[X[i]]) ADD(X[i]);
		if(mp[nxt]!=mp[X[i]]) ADD(nxt);
	}
//	for(rint i=1;i<=num1;++i) cout<<pos1[i]<<" ";
//	for(rint i=1;i<=num2;++i) cout<<pos2[i]<<" ";
	for(rint i=1;i<=num1;++i)
	{
		for(rint j=1;j<=num2;++j)
		{
			if(!vis[abs(pos1[i]-pos2[j])])
			{
				add(i,j);
			}
		}
	}int cnt=0;
	for(rint i=1;i<=num1;++i) {memset(v,0,sizeof(v));if(DFS(i)) cnt++;}
	int x=num1-cnt,y=num2-cnt;
	int ans=cnt+(x/2)*2+(y/2)*2+(x&1)*3;
	cout<<ans;
	return 0;
}
/*
by was_n
18.9.25
*/

### 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>
#define gc getchar()
#define ll long long
#define pb push_back
#define mk make_pair
#define rint register int 
using namespace std;
inline int read(){int w=1,s=0;char ch=getchar();while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}while(isdigit(ch)){s=s*10+ch-'0';ch=getchar();}return  w*s;}
struct node{
	int to,next;
}e[1000010];
int h[1000100],tot;
int X[1000010];
int N;int vis[10000010],prime[1000010],cnt;
int pos1[1000010],num1,pos2[1000010],num2;
int v[660],lk[1010];
inline void add(int from,int to){e[++tot].next=h[from];h[from]=tot;e[tot].to=to;}
inline void Init(int n)
{	vis[1]=1;
	for(rint i=2;i<=n;++i)
	{
		if(!vis[i]) prime[++cnt]=i;
		for(rint j=1;j<=cnt&&prime[j]*i<=n;++j)
		{
			vis[i*prime[j]]=1;
			if(i%prime[j]==0) break;
		}
	}vis[2]=1;
}
unordered_map<int,int> mp;
inline void ADD(int x)
{
	if(x&1) pos1[++num1]=x;
	else    pos2[++num2]=x;
}
inline bool DFS(int now)
{
	for(rint i=h[now];i;i=e[i].next)
	{
		int to=e[i].to;
		if(!v[to])
		{
			v[to]=1;
			if(!lk[to]||DFS(lk[to]))
			{
				lk[to]=now;
				return 1;
			}
		}
	}return 0;
}
int main()
{	N=read();
	for(rint i=1;i<=N;++i) X[i]=read(),mp[X[i]]=1;
	Init(1e7);
	for(rint i=1;i<=N;++i)
	{	
		int las=X[i]-1;
		int nxt=X[i]+1;
		if(mp[las]!=mp[X[i]]) ADD(X[i]);
		if(mp[nxt]!=mp[X[i]]) ADD(nxt);
	}
//	for(rint i=1;i<=num1;++i) cout<<pos1[i]<<" ";
//	for(rint i=1;i<=num2;++i) cout<<pos2[i]<<" ";
	for(rint i=1;i<=num1;++i)
	{
		for(rint j=1;j<=num2;++j)
		{
			if(!vis[abs(pos1[i]-pos2[j])])
			{
				add(i,j);
			}
		}
	}int cnt=0;
	for(rint i=1;i<=num1;++i) {memset(v,0,sizeof(v));if(DFS(i)) cnt++;}
	int x=num1-cnt,y=num2-cnt;
	int ans=cnt+(x/2)*2+(y/2)*2+(x&1)*3;
	cout<<ans;
	return 0;
}
/*
by was_n
18.9.25
*/

```