#include "bits/stdc++.h"
using namespace std;
const int N = 2e2 + 2;
const int M = 1e7 + 7;
int n;
int x[N];
int arr[N];
int siz;
bool p[M];
void pre(){
	for(int i = 2 ; i * i < M ; ++i){
		if(!p[i]){
			for(int j = i * i ; j < M ; j += i){
				p[j] = 1;
			}
		}
	}
	p[0] = 1;
	p[1] = 1;
	p[2] = 1;
}
vector < int > v[N];
int lft , rgt;
int match[N];
int timer;
int visited[N];
bool dfs(int node){
	if(visited[node] == timer){
		return 0;
	}
	visited[node] = timer;
	for(int next : v[node]){
		if(!match[next] || dfs(match[next])){
			match[next] = node;
			return 1;
		}
	}
	return 0;
}
int main(){
	pre();
	scanf("%d" , &n);
	for(int i = 1 ; i <= n ; ++i){
		scanf("%d" , x + i);
	}
	int cur = x[1];
	int str = x[1];
	for(int i = 2 ; i <= n ; ++i){
		if(cur + 1 != x[i]){
			arr[++siz] = str;
			arr[++siz] = cur + 1;
			str = x[i];
			cur = x[i];
		}
		else{
			++cur;
		}
	}
	arr[++siz] = str;
	arr[++siz] = cur + 1;
	n = siz;
	for(int i = 1 ; i <= n ; ++i){
		if(arr[i] & 1){
			++lft;
		}
		else{
			++rgt;
		}
	}
	for(int i = 1 ; i <= n ; ++i){
		if(arr[i] & 1){
			for(int j = 1 ; j <= n ; ++j){
				if(!p[abs(arr[j] - arr[i])]){
					v[i].emplace_back(j);
				}
			}
		}
	}
	int tot = 0;
	for(int i = 1 ; i <= n ; ++i){
		if(arr[i] & 1){
			++timer;
			tot += dfs(i);
		}
	}
	int ans = 0;
	ans += tot;
	ans += ((lft - tot) >> 1) << 1;
	ans += ((rgt - tot) >> 1) << 1;
	ans += ((lft - tot) & 1) * 3;
	printf("%d\n" , ans);
}
### 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 "bits/stdc++.h"
using namespace std;
const int N = 2e2 + 2;
const int M = 1e7 + 7;
int n;
int x[N];
int arr[N];
int siz;
bool p[M];
void pre(){
	for(int i = 2 ; i * i < M ; ++i){
		if(!p[i]){
			for(int j = i * i ; j < M ; j += i){
				p[j] = 1;
			}
		}
	}
	p[0] = 1;
	p[1] = 1;
	p[2] = 1;
}
vector < int > v[N];
int lft , rgt;
int match[N];
int timer;
int visited[N];
bool dfs(int node){
	if(visited[node] == timer){
		return 0;
	}
	visited[node] = timer;
	for(int next : v[node]){
		if(!match[next] || dfs(match[next])){
			match[next] = node;
			return 1;
		}
	}
	return 0;
}
int main(){
	pre();
	scanf("%d" , &n);
	for(int i = 1 ; i <= n ; ++i){
		scanf("%d" , x + i);
	}
	int cur = x[1];
	int str = x[1];
	for(int i = 2 ; i <= n ; ++i){
		if(cur + 1 != x[i]){
			arr[++siz] = str;
			arr[++siz] = cur + 1;
			str = x[i];
			cur = x[i];
		}
		else{
			++cur;
		}
	}
	arr[++siz] = str;
	arr[++siz] = cur + 1;
	n = siz;
	for(int i = 1 ; i <= n ; ++i){
		if(arr[i] & 1){
			++lft;
		}
		else{
			++rgt;
		}
	}
	for(int i = 1 ; i <= n ; ++i){
		if(arr[i] & 1){
			for(int j = 1 ; j <= n ; ++j){
				if(!p[abs(arr[j] - arr[i])]){
					v[i].emplace_back(j);
				}
			}
		}
	}
	int tot = 0;
	for(int i = 1 ; i <= n ; ++i){
		if(arr[i] & 1){
			++timer;
			tot += dfs(i);
		}
	}
	int ans = 0;
	ans += tot;
	ans += ((lft - tot) >> 1) << 1;
	ans += ((rgt - tot) >> 1) << 1;
	ans += ((lft - tot) & 1) * 3;
	printf("%d\n" , ans);
}
```