#include<bits/stdc++.h>
using namespace std;
const int N = 5010, M = 1e7+6;
int prime[M],pcnt,_v[M];
int k,x[N];
inline void sieve(int n = 10000000+2){
	_v[0]=_v[1]=1;
	for(int i=2;i<=n;i++){
		if(!_v[i])prime[++pcnt]=i;
		for(int j=1;j<=pcnt&&1ll*i*prime[j]<=n;j++){
			_v[i*prime[j]]=1;
			if(i%prime[j]==0)break;
		}
	}
}
int id1[N],id2[N],cnt1,cnt2;

struct node{int x,y,next;}edge[100010]; int len,first[N];
void adde(int x,int y){len++; edge[len].x=x; edge[len].y=y; edge[len].next=first[x]; first[x]=len;}
int chw[N],match[N];
bool dfs(int x)
{
  for(int k=first[x];k!=-1;k=edge[k].next)
  {
    int y=edge[k].y;
    if(!chw[y])
    {
      chw[y] = 1;
      if((match[y] == 0) || dfs(match[y])){match[y] = x; return 1;}
    }
  }
  return 0;
}

int main()
{
//	freopen("oatmeal.in","r",stdin);
//	freopen("oatmeal.out","w",stdout);
	sieve();
	cin >> k;
	for(int i=1;i<=k;i++){
		scanf("%d",&x[i]);
	}
	sort(x+1,x+k+1);
	for(int u=1,v;u<=k;u=v+1){
		v=u;
		while(v+1<=k&&x[v+1]==x[v]+1)++v;
		if(x[u]%2)id1[++cnt1]=x[u];
		else id2[++cnt2]=x[u];
		if((x[v]+1)%2)id1[++cnt1]=x[v]+1;
		else id2[++cnt2]=x[v]+1;
	}
	memset(first,-1,sizeof(first));
	for(int i=1;i<=cnt1;i++)for(int j=1;j<=cnt2;j++){
		if(!_v[abs(id1[i]-id2[j])]){
			adde(i,j);
			// cout << "?" << endl;
		}
	}
	// cout << cnt << endl;
	int ans=0;
	for(int i=1;i<=cnt1;i++){
		for(int j=1;j<N;j++)chw[j]=0;
		if(dfs(i))ans++;
	}
	//cout << cnt1 << " " << cnt2 << " " << ans << endl;
	cnt1-=ans,cnt2-=ans;
	if(cnt1%2==0){
		cout << cnt1+cnt2+ans << endl;
	}else{
		cout << cnt1+cnt2+ans+1 << endl;
	}
}

### Prompt

Please formulate 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;
const int N = 5010, M = 1e7+6;
int prime[M],pcnt,_v[M];
int k,x[N];
inline void sieve(int n = 10000000+2){
	_v[0]=_v[1]=1;
	for(int i=2;i<=n;i++){
		if(!_v[i])prime[++pcnt]=i;
		for(int j=1;j<=pcnt&&1ll*i*prime[j]<=n;j++){
			_v[i*prime[j]]=1;
			if(i%prime[j]==0)break;
		}
	}
}
int id1[N],id2[N],cnt1,cnt2;

struct node{int x,y,next;}edge[100010]; int len,first[N];
void adde(int x,int y){len++; edge[len].x=x; edge[len].y=y; edge[len].next=first[x]; first[x]=len;}
int chw[N],match[N];
bool dfs(int x)
{
  for(int k=first[x];k!=-1;k=edge[k].next)
  {
    int y=edge[k].y;
    if(!chw[y])
    {
      chw[y] = 1;
      if((match[y] == 0) || dfs(match[y])){match[y] = x; return 1;}
    }
  }
  return 0;
}

int main()
{
//	freopen("oatmeal.in","r",stdin);
//	freopen("oatmeal.out","w",stdout);
	sieve();
	cin >> k;
	for(int i=1;i<=k;i++){
		scanf("%d",&x[i]);
	}
	sort(x+1,x+k+1);
	for(int u=1,v;u<=k;u=v+1){
		v=u;
		while(v+1<=k&&x[v+1]==x[v]+1)++v;
		if(x[u]%2)id1[++cnt1]=x[u];
		else id2[++cnt2]=x[u];
		if((x[v]+1)%2)id1[++cnt1]=x[v]+1;
		else id2[++cnt2]=x[v]+1;
	}
	memset(first,-1,sizeof(first));
	for(int i=1;i<=cnt1;i++)for(int j=1;j<=cnt2;j++){
		if(!_v[abs(id1[i]-id2[j])]){
			adde(i,j);
			// cout << "?" << endl;
		}
	}
	// cout << cnt << endl;
	int ans=0;
	for(int i=1;i<=cnt1;i++){
		for(int j=1;j<N;j++)chw[j]=0;
		if(dfs(i))ans++;
	}
	//cout << cnt1 << " " << cnt2 << " " << ans << endl;
	cnt1-=ans,cnt2-=ans;
	if(cnt1%2==0){
		cout << cnt1+cnt2+ans << endl;
	}else{
		cout << cnt1+cnt2+ans+1 << endl;
	}
}

```