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

namespace prime{
	const int mx = 10000001;
	bool f[mx];
	int p[777777],lp;
	void init(){
		for(int i=2; i<mx; i++){
			if(!f[i])p[lp++]=i;
			for(int j=0; j<lp; j++){
				int w = p[j] * i;
				if(w >= mx)break;
				f[w] = true;
				if(i%p[j]==0)break;
			}
		}
	}
	bool isprime(int x){
		if(x<2)return false;
		return !f[x];
	}
};

bool g[10000002];

int lk[333];
bool b[333];
int A[333],B[333],LA,LB;
bool fd(int x){
	for(int j=0; j<LB; j++)
		if(!b[j] && prime::isprime(labs(A[x]-B[j]))){
			b[j] = true;
			if(lk[j] == -1 || fd(lk[j])){
				lk[j] = x;
				return true;
			}
		}
	return false;
}
int main(){
	prime::init();
	int x,z;
	for(scanf("%d",&x); x--;){
		scanf("%d",&z);
		g[z] = true;
	}
	for(int i=0; i<=z; i++)if(g[i] != g[i+1]){
		if(i%2==0)A[LA++] = i;else
			B[LB++] = i;
	}
	memset(lk,-1,sizeof(lk));
	int R = 0;
	for(int i=0; i<LA; i++){
		memset(b,0,sizeof(b));
		if(fd(i))R++;
	}
	LA -= R;
	LB -= R;
	if(LA % 2 == 1)R += 3;
	R += LA / 2 * 2 + LB / 2 * 2;
	printf("%d\n",R);
	return 0;
}

### Prompt

Your task is to create 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>
using namespace std;

namespace prime{
	const int mx = 10000001;
	bool f[mx];
	int p[777777],lp;
	void init(){
		for(int i=2; i<mx; i++){
			if(!f[i])p[lp++]=i;
			for(int j=0; j<lp; j++){
				int w = p[j] * i;
				if(w >= mx)break;
				f[w] = true;
				if(i%p[j]==0)break;
			}
		}
	}
	bool isprime(int x){
		if(x<2)return false;
		return !f[x];
	}
};

bool g[10000002];

int lk[333];
bool b[333];
int A[333],B[333],LA,LB;
bool fd(int x){
	for(int j=0; j<LB; j++)
		if(!b[j] && prime::isprime(labs(A[x]-B[j]))){
			b[j] = true;
			if(lk[j] == -1 || fd(lk[j])){
				lk[j] = x;
				return true;
			}
		}
	return false;
}
int main(){
	prime::init();
	int x,z;
	for(scanf("%d",&x); x--;){
		scanf("%d",&z);
		g[z] = true;
	}
	for(int i=0; i<=z; i++)if(g[i] != g[i+1]){
		if(i%2==0)A[LA++] = i;else
			B[LB++] = i;
	}
	memset(lk,-1,sizeof(lk));
	int R = 0;
	for(int i=0; i<LA; i++){
		memset(b,0,sizeof(b));
		if(fd(i))R++;
	}
	LA -= R;
	LB -= R;
	if(LA % 2 == 1)R += 3;
	R += LA / 2 * 2 + LB / 2 * 2;
	printf("%d\n",R);
	return 0;
}

```