#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<bitset>
using namespace std;
typedef long long LL;
const int N=1e5,M=1e7+1;
int gi() {
	int w=0;bool q=1;char c=getchar();
	while ((c<'0'||c>'9') && c!='-') c=getchar();
	if (c=='-') q=0,c=getchar();
	while (c>='0'&&c <= '9') w=w*10+c-'0',c=getchar();
	return q? w:-w;
}

int n;
int match[N],pre[N],q[N],vis[N],cnt;
int x[N];vector<int>e[N];

inline bool bfs(int k) {
	queue<int>q;
	++cnt;q.push(k);
	while (!q.empty()) {
		k=q.front();q.pop();
		for (int t:e[k]) if (vis[t]!=cnt) {
				if (match[t]) {
					vis[t]=cnt;
					pre[match[t]]=k;
					q.push(match[t]);
				} else {
					int p;
					while (k) {
						p=match[k];
						match[k]=t,match[t]=k;
						t=p,k=pre[k];
					}
					return true;
				}
			}
	}
	return false;
}

int pri[M];
bool in[M];
inline void init(int n) {
	int i,j,len=0;
	for (i=2;i<=n;i++) {
		if (!pri[i]) pri[++len]=i,in[i]=i!=2;
		for (j=1;j<=len&&i*pri[j]<=n;j++) {
			pri[i*pri[j]]=1;
			if (!(i%pri[j])) break;
		}
	}
}
int main()
{
	n=gi();int i,j,odd=0,s=0,m=0;
	for (i=1;i<=n;i++) x[++m]=gi(),x[m+1]=x[m]+1,m++;
	sort(x+1,x+1+m);
	for (i=1,n=0;i<=m;i++) if (x[i]==x[i+1]) i++; else x[++n]=x[i];
	
	init(x[n]-x[1]);

	for (i=1;i<=n;i++)
		if (x[i]&1) {
			odd++;
			for (j=1;j<=n;j++)
				if (in[abs(x[j]-x[i])])
					e[i].push_back(j);
		}
	for (i=1;i<=n;i++) if (x[i]&1) s+=bfs(i);

	cout<<n-s+((s-odd)&1);
	return 0;
}

### Prompt

Please create a solution in Cpp 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<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<bitset>
using namespace std;
typedef long long LL;
const int N=1e5,M=1e7+1;
int gi() {
	int w=0;bool q=1;char c=getchar();
	while ((c<'0'||c>'9') && c!='-') c=getchar();
	if (c=='-') q=0,c=getchar();
	while (c>='0'&&c <= '9') w=w*10+c-'0',c=getchar();
	return q? w:-w;
}

int n;
int match[N],pre[N],q[N],vis[N],cnt;
int x[N];vector<int>e[N];

inline bool bfs(int k) {
	queue<int>q;
	++cnt;q.push(k);
	while (!q.empty()) {
		k=q.front();q.pop();
		for (int t:e[k]) if (vis[t]!=cnt) {
				if (match[t]) {
					vis[t]=cnt;
					pre[match[t]]=k;
					q.push(match[t]);
				} else {
					int p;
					while (k) {
						p=match[k];
						match[k]=t,match[t]=k;
						t=p,k=pre[k];
					}
					return true;
				}
			}
	}
	return false;
}

int pri[M];
bool in[M];
inline void init(int n) {
	int i,j,len=0;
	for (i=2;i<=n;i++) {
		if (!pri[i]) pri[++len]=i,in[i]=i!=2;
		for (j=1;j<=len&&i*pri[j]<=n;j++) {
			pri[i*pri[j]]=1;
			if (!(i%pri[j])) break;
		}
	}
}
int main()
{
	n=gi();int i,j,odd=0,s=0,m=0;
	for (i=1;i<=n;i++) x[++m]=gi(),x[m+1]=x[m]+1,m++;
	sort(x+1,x+1+m);
	for (i=1,n=0;i<=m;i++) if (x[i]==x[i+1]) i++; else x[++n]=x[i];
	
	init(x[n]-x[1]);

	for (i=1;i<=n;i++)
		if (x[i]&1) {
			odd++;
			for (j=1;j<=n;j++)
				if (in[abs(x[j]-x[i])])
					e[i].push_back(j);
		}
	for (i=1;i<=n;i++) if (x[i]&1) s+=bfs(i);

	cout<<n-s+((s-odd)&1);
	return 0;
}

```