#include<bits/stdc++.h>
#define maxn 205
#define maxp 10000007
using namespace std;

int a[maxn],cnt,n;
int pr[maxp],vis[maxp],cnt_pr;
int usd[maxn],mat[maxn];

int dfs(int u){
	for(int i=1;i<=cnt;i++) if(vis[abs(a[u]-a[i])] == 0 && !usd[i]){
		usd[i] = 1;
		if(!mat[i] || dfs(mat[i])){
			mat[i] = u , mat[u] = i;
			return 1;
		}
	}
	return 0;
}

int main(){
	for(int i=2;i<maxp;i++){
		if(!vis[i]) pr[cnt_pr++] = i;
		for(int j=0;pr[j]*i<maxp;j++){
			vis[i*pr[j]] = 1;
			if(i % pr[j] == 0) break;
		}
	}
	vis[2] = vis[0] = vis[1] = 1;
	scanf("%d",&n);
	int p = -10;
	for(int i=1;i<=n;i++){int x;
		scanf("%d",&x);
		if(x != p + 1){
			if(p>0)a[++cnt] = p + 1;
			a[++cnt] = x;
		}
		p = x;
	}
	a[++cnt] = p+1;
	int s[2] = {};
	for(int i=1;i<=cnt;i++) assert(a[i] > 0) , s[a[i] % 2] ++;
	int ans = 0;
	for(int i=1;i<=cnt;i++) if(a[i]%2 && !mat[i]) memset(usd,0,sizeof usd),ans += dfs(i);
	ans += 2 * ((s[0] - ans) / 2 + (s[1] - ans) / 2);
	ans += 3 * ((s[0] - ans) % 2 && (s[1] - ans) % 2);
	printf("%d\n",ans);
}
### 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<bits/stdc++.h>
#define maxn 205
#define maxp 10000007
using namespace std;

int a[maxn],cnt,n;
int pr[maxp],vis[maxp],cnt_pr;
int usd[maxn],mat[maxn];

int dfs(int u){
	for(int i=1;i<=cnt;i++) if(vis[abs(a[u]-a[i])] == 0 && !usd[i]){
		usd[i] = 1;
		if(!mat[i] || dfs(mat[i])){
			mat[i] = u , mat[u] = i;
			return 1;
		}
	}
	return 0;
}

int main(){
	for(int i=2;i<maxp;i++){
		if(!vis[i]) pr[cnt_pr++] = i;
		for(int j=0;pr[j]*i<maxp;j++){
			vis[i*pr[j]] = 1;
			if(i % pr[j] == 0) break;
		}
	}
	vis[2] = vis[0] = vis[1] = 1;
	scanf("%d",&n);
	int p = -10;
	for(int i=1;i<=n;i++){int x;
		scanf("%d",&x);
		if(x != p + 1){
			if(p>0)a[++cnt] = p + 1;
			a[++cnt] = x;
		}
		p = x;
	}
	a[++cnt] = p+1;
	int s[2] = {};
	for(int i=1;i<=cnt;i++) assert(a[i] > 0) , s[a[i] % 2] ++;
	int ans = 0;
	for(int i=1;i<=cnt;i++) if(a[i]%2 && !mat[i]) memset(usd,0,sizeof usd),ans += dfs(i);
	ans += 2 * ((s[0] - ans) / 2 + (s[1] - ans) / 2);
	ans += 3 * ((s[0] - ans) % 2 && (s[1] - ans) % 2);
	printf("%d\n",ans);
}
```