#include<bits/stdc++.h>
using namespace std;

const int _ = 1e7 + 7;
bool nprm[_]; int arr[_] , N; vector < int > ch[2] , Ed[3003];

void shai(int mx){
	nprm[1] = 1;
	for(int i = 2 ; i <= mx ; ++i)
		if(!nprm[i]) for(int j = i ; j <= mx / i ; ++j) nprm[i * j] = 1;
}

int match[3003]; bool vis[3003];

bool dfs(int x){
	for(int i = 0 ; i < Ed[x].size() ; ++i)
		if(!vis[Ed[x][i]]){vis[Ed[x][i]] = 1; if(match[Ed[x][i]] == -1 || dfs(match[Ed[x][i]])){match[Ed[x][i]] = x; return 1;}}
	return 0;
}

int main(){
	scanf("%d" , &N); int mx = 0; for(int i = 1 , p ; i <= N ; ++i){scanf("%d" , &p); arr[p] = 1; mx = max(mx , p + 1);}
	shai(mx); for(int i = 1 ; i <= mx ; ++i) if(arr[i] ^ arr[i - 1]) ch[i & 1].push_back(i);
	for(int i = 0 ; i < ch[0].size() ; ++i)
		for(int j = 0 ; j < ch[1].size() ; ++j)
			if(!nprm[abs(ch[1][j] - ch[0][i])]) Ed[i].push_back(j);
	memset(match , -1 , sizeof(match)); int ans = 0;
	for(int i = 0 ; i < ch[0].size() ; ++i){memset(vis , 0 , sizeof(vis)); ans += dfs(i);}
	cout << (ans + ((ch[0].size() - ans) / 2 + (ch[1].size() - ans) / 2) * 2 + ((ch[0].size() - ans) & 1) * 3); 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<bits/stdc++.h>
using namespace std;

const int _ = 1e7 + 7;
bool nprm[_]; int arr[_] , N; vector < int > ch[2] , Ed[3003];

void shai(int mx){
	nprm[1] = 1;
	for(int i = 2 ; i <= mx ; ++i)
		if(!nprm[i]) for(int j = i ; j <= mx / i ; ++j) nprm[i * j] = 1;
}

int match[3003]; bool vis[3003];

bool dfs(int x){
	for(int i = 0 ; i < Ed[x].size() ; ++i)
		if(!vis[Ed[x][i]]){vis[Ed[x][i]] = 1; if(match[Ed[x][i]] == -1 || dfs(match[Ed[x][i]])){match[Ed[x][i]] = x; return 1;}}
	return 0;
}

int main(){
	scanf("%d" , &N); int mx = 0; for(int i = 1 , p ; i <= N ; ++i){scanf("%d" , &p); arr[p] = 1; mx = max(mx , p + 1);}
	shai(mx); for(int i = 1 ; i <= mx ; ++i) if(arr[i] ^ arr[i - 1]) ch[i & 1].push_back(i);
	for(int i = 0 ; i < ch[0].size() ; ++i)
		for(int j = 0 ; j < ch[1].size() ; ++j)
			if(!nprm[abs(ch[1][j] - ch[0][i])]) Ed[i].push_back(j);
	memset(match , -1 , sizeof(match)); int ans = 0;
	for(int i = 0 ; i < ch[0].size() ; ++i){memset(vis , 0 , sizeof(vis)); ans += dfs(i);}
	cout << (ans + ((ch[0].size() - ans) / 2 + (ch[1].size() - ans) / 2) * 2 + ((ch[0].size() - ans) & 1) * 3); return 0;
}
```