#include<cstdio>
using namespace std;
int cnt,last[205],a[205],b[205],x[205],vis[205],match[205],prime[10000005],isprime[10000005],s[10000005];
struct node{
	int to,next;
}e[1000005];
void add(int a,int b){
	e[++cnt].to=b;
	e[cnt].next=last[a];
	last[a]=cnt;
}
int dfs(int x){
	for (int i=last[x]; i; i=e[i].next){
		int V=e[i].to;
		if (!vis[V]){
			vis[V]=1;
			if (!match[V] || dfs(match[V])){
				match[V]=x;
				return 1;
			}
		}
	}
	return 0;
}
int abs1(int x){
	if (x<0) return -x;
	return x;
}
int main(){
	isprime[1]=1;
	for (int i=2; i<=10000000; i++){
		if (!isprime[i]) prime[++cnt]=i;
		for (int j=1; j<=cnt && i*prime[j]<=10000000; j++){
			isprime[i*prime[j]]=1;
			if (i%prime[j]==0) break;
		}
	}
	int n;
	scanf("%d",&n);
	for (int i=1; i<=n; i++){
		scanf("%d",&x[i]);
		s[x[i]]^=1;
	}
	int num=0,sum=0;
	for (int i=1; i<=10000001; i++)
		if (s[i]!=s[i-1]){
			if (i%2==1) a[++num]=i;
			else b[++sum]=i;
		}
	for (int i=1; i<=num; i++)
		for (int j=1; j<=sum; j++)
			if (!isprime[abs1(a[i]-b[j])]) add(i,j);
	int ss=0;
	for (int i=1; i<=num; i++){
		for (int j=1; j<=sum; j++) vis[j]=0;
		if (dfs(i)) ss++;
	}
	int ans=(num-ss)/2*2+(sum-ss)/2*2+ss+((num&1)!=(ss&1)?3:0);
	printf("%d\n",ans);
	return 0;
}

### Prompt

Generate 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>
using namespace std;
int cnt,last[205],a[205],b[205],x[205],vis[205],match[205],prime[10000005],isprime[10000005],s[10000005];
struct node{
	int to,next;
}e[1000005];
void add(int a,int b){
	e[++cnt].to=b;
	e[cnt].next=last[a];
	last[a]=cnt;
}
int dfs(int x){
	for (int i=last[x]; i; i=e[i].next){
		int V=e[i].to;
		if (!vis[V]){
			vis[V]=1;
			if (!match[V] || dfs(match[V])){
				match[V]=x;
				return 1;
			}
		}
	}
	return 0;
}
int abs1(int x){
	if (x<0) return -x;
	return x;
}
int main(){
	isprime[1]=1;
	for (int i=2; i<=10000000; i++){
		if (!isprime[i]) prime[++cnt]=i;
		for (int j=1; j<=cnt && i*prime[j]<=10000000; j++){
			isprime[i*prime[j]]=1;
			if (i%prime[j]==0) break;
		}
	}
	int n;
	scanf("%d",&n);
	for (int i=1; i<=n; i++){
		scanf("%d",&x[i]);
		s[x[i]]^=1;
	}
	int num=0,sum=0;
	for (int i=1; i<=10000001; i++)
		if (s[i]!=s[i-1]){
			if (i%2==1) a[++num]=i;
			else b[++sum]=i;
		}
	for (int i=1; i<=num; i++)
		for (int j=1; j<=sum; j++)
			if (!isprime[abs1(a[i]-b[j])]) add(i,j);
	int ss=0;
	for (int i=1; i<=num; i++){
		for (int j=1; j<=sum; j++) vis[j]=0;
		if (dfs(i)) ss++;
	}
	int ans=(num-ss)/2*2+(sum-ss)/2*2+ss+((num&1)!=(ss&1)?3:0);
	printf("%d\n",ans);
	return 0;
}

```