#include <string>
#include<queue>
#include<iostream>
#include<set>
#include<vector>
#include<algorithm>
#include<map>
#include<tuple>

using namespace std;

typedef pair<int,int> pii;
typedef tuple<int,int,int> t3;
typedef tuple<int,int,int,int> t4;

const int MX = 205;

int D[MX];
vector<int> L[MX];
int R[MX];
int vst[MX], t = 1;

int dfs(int x){
	if( vst[x] == t ) return 0;
	vst[x] = t;
	for(int c : L[x]){
		if( !R[c] || dfs(R[c])){
			R[c] = x;
			return 1;
		}
	}
	return 0;
}

int is_prime(int a){
	if( a < 0) a = -a;
	if( a == 1 ) return false;
	for(int i = 2; i*i <= a; i++) if( a%i == 0 ) return false;
	return true;
}

int main()
{
	int N;
	scanf("%d", &N);
	for(int i = 1; i <= N; i++){
		scanf("%d", D+i);
	}

	int M = 1, E[MX] = {0, D[1]};
	for(int i = 2; i <= N; i++){
		if( D[i-1] != D[i]-1){
			E[++M] = D[i-1]+1;
			E[++M] = D[i];
		}
	}
	E[++M] = D[N]+1;

	int a = 0, b = 0;
	for(int i = 1; i <= M; i++){
		if( E[i]%2 == 0) a++;
		else b++;
	}
	for(int i = 1; i <= M; i++){
		for(int j = 1; j <= M; j++){
			if( E[i]%2 == 0 && E[j]%2 == 1 );
			else continue;
			if( is_prime(E[i] - E[j]) ) L[i].push_back(j);
		}
	}
	int ans = 0;
	for(int i = 1; i <= M; i++){
		t++; if(dfs(i)) ans++, a--, b--;
	}
	ans += (a/2 + b/2) * 2;
	if( a%2 == 1 ) ans += 3;
	printf("%d\n", ans);
}

### Prompt

Your challenge is to write 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 <string>
#include<queue>
#include<iostream>
#include<set>
#include<vector>
#include<algorithm>
#include<map>
#include<tuple>

using namespace std;

typedef pair<int,int> pii;
typedef tuple<int,int,int> t3;
typedef tuple<int,int,int,int> t4;

const int MX = 205;

int D[MX];
vector<int> L[MX];
int R[MX];
int vst[MX], t = 1;

int dfs(int x){
	if( vst[x] == t ) return 0;
	vst[x] = t;
	for(int c : L[x]){
		if( !R[c] || dfs(R[c])){
			R[c] = x;
			return 1;
		}
	}
	return 0;
}

int is_prime(int a){
	if( a < 0) a = -a;
	if( a == 1 ) return false;
	for(int i = 2; i*i <= a; i++) if( a%i == 0 ) return false;
	return true;
}

int main()
{
	int N;
	scanf("%d", &N);
	for(int i = 1; i <= N; i++){
		scanf("%d", D+i);
	}

	int M = 1, E[MX] = {0, D[1]};
	for(int i = 2; i <= N; i++){
		if( D[i-1] != D[i]-1){
			E[++M] = D[i-1]+1;
			E[++M] = D[i];
		}
	}
	E[++M] = D[N]+1;

	int a = 0, b = 0;
	for(int i = 1; i <= M; i++){
		if( E[i]%2 == 0) a++;
		else b++;
	}
	for(int i = 1; i <= M; i++){
		for(int j = 1; j <= M; j++){
			if( E[i]%2 == 0 && E[j]%2 == 1 );
			else continue;
			if( is_prime(E[i] - E[j]) ) L[i].push_back(j);
		}
	}
	int ans = 0;
	for(int i = 1; i <= M; i++){
		t++; if(dfs(i)) ans++, a--, b--;
	}
	ans += (a/2 + b/2) * 2;
	if( a%2 == 1 ) ans += 3;
	printf("%d\n", ans);
}

```