#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <memory.h>
#include <queue>

using namespace std;
typedef long long LL;
const int maxn = 10000005;
const int maxm = 505;

int prm[maxn/10],tot;bool is[maxn];
int n,x[maxm],a[maxm],m,e[maxm][maxm];
int match[maxm],vis[maxm],ans,odd,even;
void predo(int n) {
	is[0]=is[1]=1;
	for (int i=2;i<=n;i++)
	{
		if (!is[i]) prm[++tot]=i;
		for (int j=1;j<=tot;j++)
		{
			int num=prm[j]*i;
			if (num>n) break;
			if (i%prm[j]) is[num]=1;
			else {is[num]=1;break;}
		}
	}
}
bool Hungray(int u) {
	for (int v=1;v<=m;v++)
	if (e[u][v]&&!vis[v]) {
		vis[v]=true;
		if (!match[v]||Hungray(match[v])) {
			match[v]=u;return true;
		}
	}
	return false;
}
int main()
{
	#ifdef Amberframe
		freopen("arc080f.in","r",stdin);
		freopen("arc080f.out","w",stdout);
	#endif
	predo(1e7);scanf("%d",&n);x[0]=-1;
	for (int i=1;i<=n;i++) scanf("%d",&x[i]);
	for (int i=1;i<=n;i++) x[i]!=x[i-1]+1?a[++m]=x[i]:0;
	for (int i=1;i<=n;i++) x[i]!=x[i+1]-1?a[++m]=x[i]+1:0;
	sort(a+1,a+m+1);is[2]=1;
	for (int i=1;i<=m;i++)
	for (int j=i+1;j<=m;j++)
		if (!is[a[j]-a[i]]) e[i][j]=e[j][i]=1;
	for (int i=1;i<=m;i++)
	if (a[i]&1) {
		++odd;memset(vis,0,sizeof vis);
		if (Hungray(i)) ++ans;
	}
	else ++even;
	odd-=ans;even-=ans;
	ans+=2*(odd/2+even/2)+(odd&1)*3;
	printf("%d",ans);
	return 0;
}
### Prompt

Please provide a cpp coded solution to the problem described below:

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 <stdio.h>
#include <iostream>
#include <algorithm>
#include <memory.h>
#include <queue>

using namespace std;
typedef long long LL;
const int maxn = 10000005;
const int maxm = 505;

int prm[maxn/10],tot;bool is[maxn];
int n,x[maxm],a[maxm],m,e[maxm][maxm];
int match[maxm],vis[maxm],ans,odd,even;
void predo(int n) {
	is[0]=is[1]=1;
	for (int i=2;i<=n;i++)
	{
		if (!is[i]) prm[++tot]=i;
		for (int j=1;j<=tot;j++)
		{
			int num=prm[j]*i;
			if (num>n) break;
			if (i%prm[j]) is[num]=1;
			else {is[num]=1;break;}
		}
	}
}
bool Hungray(int u) {
	for (int v=1;v<=m;v++)
	if (e[u][v]&&!vis[v]) {
		vis[v]=true;
		if (!match[v]||Hungray(match[v])) {
			match[v]=u;return true;
		}
	}
	return false;
}
int main()
{
	#ifdef Amberframe
		freopen("arc080f.in","r",stdin);
		freopen("arc080f.out","w",stdout);
	#endif
	predo(1e7);scanf("%d",&n);x[0]=-1;
	for (int i=1;i<=n;i++) scanf("%d",&x[i]);
	for (int i=1;i<=n;i++) x[i]!=x[i-1]+1?a[++m]=x[i]:0;
	for (int i=1;i<=n;i++) x[i]!=x[i+1]-1?a[++m]=x[i]+1:0;
	sort(a+1,a+m+1);is[2]=1;
	for (int i=1;i<=m;i++)
	for (int j=i+1;j<=m;j++)
		if (!is[a[j]-a[i]]) e[i][j]=e[j][i]=1;
	for (int i=1;i<=m;i++)
	if (a[i]&1) {
		++odd;memset(vis,0,sizeof vis);
		if (Hungray(i)) ++ans;
	}
	else ++even;
	odd-=ans;even-=ans;
	ans+=2*(odd/2+even/2)+(odd&1)*3;
	printf("%d",ans);
	return 0;
}
```