#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxv=1e7;
const int maxn=100;
int n,cnt_a,cnt_b,tot,cnt;
int V[maxn+8],a[maxn+8],b[maxn+8],prime[maxv+8],match[maxn+8];
bool map[maxn+8][maxn+8],vis[maxv+8],inq[maxn+8];

int read()
{
    int x=0,f=1;char ch=getchar();
    for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
    for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
    return x*f;
}

void add(int x){x&1?a[++cnt_a]=x:b[++cnt_b]=x;}

void prepare()
{
    vis[1]=1;
    for (int i=2;i<=maxv+1;i++)
	{
	    if (!vis[i]) prime[++tot]=i;
	    for (int j=1;j<=tot&&1ll*prime[j]*i<=maxv+1;j++)
		{
		    vis[prime[j]*i]=1;
		    if (i%prime[j]==0) break;
		}
	}
}

bool extra(int x)
{
    for (int i=1;i<=cnt_b;i++)
	{
	    if (inq[i]||(map[x][i]==0)) continue;
	    inq[i]=1;
	    if ((!match[i])||(extra(match[i])))
		{
		    match[i]=x;
		    return 1;
		}
	}
    return 0;
}

void solve()
{
    int ans=0,rest_a=cnt_a,rest_b=cnt_b;
    for (int i=1;i<=cnt_a;i++)
	{
	    memset(inq,0,sizeof(inq));
	    if (extra(i)) ans++;
	}
    for (int i=1;i<=cnt_b;i++) if (match[i]) rest_a--,rest_b--;
    ans+=rest_a+rest_b+(rest_a&1);
    printf("%d\n",ans);
}

int main()
{
    n=read();
    for (int i=1;i<=n;i++) V[i]=read();
    sort(V+1,V+n+1);
    add(V[1]);
    for (int i=2;i<=n;i++)if (V[i]!=V[i-1]+1) add(V[i-1]+1),add(V[i]);add(V[n]+1);
    prepare();
    for (int i=1;i<=cnt_a;i++)
	for (int j=1;j<=cnt_b;j++)
	    map[i][j]=!vis[abs(a[i]-b[j])];
    solve();
}

### Prompt

Please formulate 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<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxv=1e7;
const int maxn=100;
int n,cnt_a,cnt_b,tot,cnt;
int V[maxn+8],a[maxn+8],b[maxn+8],prime[maxv+8],match[maxn+8];
bool map[maxn+8][maxn+8],vis[maxv+8],inq[maxn+8];

int read()
{
    int x=0,f=1;char ch=getchar();
    for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
    for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
    return x*f;
}

void add(int x){x&1?a[++cnt_a]=x:b[++cnt_b]=x;}

void prepare()
{
    vis[1]=1;
    for (int i=2;i<=maxv+1;i++)
	{
	    if (!vis[i]) prime[++tot]=i;
	    for (int j=1;j<=tot&&1ll*prime[j]*i<=maxv+1;j++)
		{
		    vis[prime[j]*i]=1;
		    if (i%prime[j]==0) break;
		}
	}
}

bool extra(int x)
{
    for (int i=1;i<=cnt_b;i++)
	{
	    if (inq[i]||(map[x][i]==0)) continue;
	    inq[i]=1;
	    if ((!match[i])||(extra(match[i])))
		{
		    match[i]=x;
		    return 1;
		}
	}
    return 0;
}

void solve()
{
    int ans=0,rest_a=cnt_a,rest_b=cnt_b;
    for (int i=1;i<=cnt_a;i++)
	{
	    memset(inq,0,sizeof(inq));
	    if (extra(i)) ans++;
	}
    for (int i=1;i<=cnt_b;i++) if (match[i]) rest_a--,rest_b--;
    ans+=rest_a+rest_b+(rest_a&1);
    printf("%d\n",ans);
}

int main()
{
    n=read();
    for (int i=1;i<=n;i++) V[i]=read();
    sort(V+1,V+n+1);
    add(V[1]);
    for (int i=2;i<=n;i++)if (V[i]!=V[i-1]+1) add(V[i-1]+1),add(V[i]);add(V[n]+1);
    prepare();
    for (int i=1;i<=cnt_a;i++)
	for (int j=1;j<=cnt_b;j++)
	    map[i][j]=!vis[abs(a[i]-b[j])];
    solve();
}

```