#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
struct edge{
	int k,next;
}e[1000005];
int n,a[1005],x[1005],m,home[1005],cnt=-1,flag[1005],y[1005];
bool vis[10000005];
void add(int x,int y){
	cnt++;
	e[cnt].k=y;
	e[cnt].next=home[x];
	home[x]=cnt;
}
int prime[10000005],cc=-1;
bool isprime[10000005];
void init(){
	isprime[1]=1;
	for(int i=2;i<=10000002;i++){
		if(!isprime[i]){
			prime[++cc]=i;
		}
		for(int p=1;p<=cc&&prime[p]*i<=10000002;p++){
			isprime[prime[p]*i]=1;
			if(i%prime[p]==0) break;
		}
	}
}
int Abs(int a){return a<0?-a:a;}
bool used[2005];
bool dfs(int k){
	for(int i=home[k];~i;i=e[i].next) if(!used[e[i].k]){
		used[e[i].k]=1;
		if(!flag[e[i].k]||dfs(flag[e[i].k])){
			flag[e[i].k]=k;
			return 1;
		}
	}
	return 0;
}
int main(){
	init();
	memset(home,-1,sizeof(home));
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),vis[a[i]]=1;
	int o=a[n]+1;n=0;
	for(int i=1;i<=o;i++) if(vis[i]!=vis[i-1]){
		if(i&1) x[++n]=i;
		else y[++m]=i;
	}
	for(int i=1;i<=n;i++){
		for(int p=1;p<=m;p++) if(!isprime[Abs(x[i]-y[p])]) add(i,p);
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		memset(used,0,sizeof(used));
		if(dfs(i)) ans++;
	}
	ans+=(n-ans)/2*2+(m-ans)/2*2;
	n=(n-ans)%2;m=(m-ans)%2;
	if(n&&m) ans+=3;
	printf("%d",ans);
	return 0;
}
### Prompt

Create a solution in cpp for 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 <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
struct edge{
	int k,next;
}e[1000005];
int n,a[1005],x[1005],m,home[1005],cnt=-1,flag[1005],y[1005];
bool vis[10000005];
void add(int x,int y){
	cnt++;
	e[cnt].k=y;
	e[cnt].next=home[x];
	home[x]=cnt;
}
int prime[10000005],cc=-1;
bool isprime[10000005];
void init(){
	isprime[1]=1;
	for(int i=2;i<=10000002;i++){
		if(!isprime[i]){
			prime[++cc]=i;
		}
		for(int p=1;p<=cc&&prime[p]*i<=10000002;p++){
			isprime[prime[p]*i]=1;
			if(i%prime[p]==0) break;
		}
	}
}
int Abs(int a){return a<0?-a:a;}
bool used[2005];
bool dfs(int k){
	for(int i=home[k];~i;i=e[i].next) if(!used[e[i].k]){
		used[e[i].k]=1;
		if(!flag[e[i].k]||dfs(flag[e[i].k])){
			flag[e[i].k]=k;
			return 1;
		}
	}
	return 0;
}
int main(){
	init();
	memset(home,-1,sizeof(home));
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),vis[a[i]]=1;
	int o=a[n]+1;n=0;
	for(int i=1;i<=o;i++) if(vis[i]!=vis[i-1]){
		if(i&1) x[++n]=i;
		else y[++m]=i;
	}
	for(int i=1;i<=n;i++){
		for(int p=1;p<=m;p++) if(!isprime[Abs(x[i]-y[p])]) add(i,p);
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		memset(used,0,sizeof(used));
		if(dfs(i)) ans++;
	}
	ans+=(n-ans)/2*2+(m-ans)/2*2;
	n=(n-ans)%2;m=(m-ans)%2;
	if(n&&m) ans+=3;
	printf("%d",ans);
	return 0;
}
```