// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define maxn 10000010
using namespace std;
int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch-'0'<0||ch-'0'>9){if(ch=='-') f=-1;ch=getchar();}
    while(ch-'0'>=0&&ch-'0'<=9){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n;
int prime[maxn],primesize;
bool isprime[maxn];
void get_prime()
{
    memset(isprime,true,sizeof(isprime));
    isprime[1]=false;
    for(int i=2;i<=maxn-10;i++)
    {
        if(isprime[i])  prime[++primesize]=i;
        for(int j=1;j<=primesize&&i*prime[j]<=maxn-10;j++)
        {
            isprime[i*prime[j]]=false;
            if(i%prime[j]==0)  break;
        }
    }
}
int s[maxn];
int a[101],b[201];
int top1,top2;
int re[101][101];
int match[101];
int vis[101];
bool dfs(int x)
{
    for(int i=1;i<=top2;i++)
    {
        if(re[x][i]&&!vis[i])
        {
            vis[i]=1;
            if(!match[i]||dfs(match[i]))
            {
                match[i]=x;
                return true;
            }
        }
    }
    return false;
}
int main()
{
    get_prime();
    n=read();
    for(int i=1;i<=n;i++)  s[read()]^=1;
    for(int i=1;i<=maxn-9;i++)
    {
        if(s[i]!=s[i-1])
        {
            if(i&1)  a[++top1]=i;
            else     b[++top2]=i;
        }
    }
    for(int i=1;i<=top1;i++)
      for(int j=1;j<=top2;j++)  if(isprime[abs(a[i]-b[j])])  re[i][j]=1;
    int a=0;
    for(int i=1;i<=top1;i++)
    {
        memset(vis,0,sizeof(vis));
        if(dfs(i))  a++;
    }
    printf("%d\n",a+((top1-a)/2)*2+((top2-a)/2)*2+(top1-a)%2*(top2-a)%2*3);
    return 0;
}
### Prompt

Your challenge is to write 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
// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define maxn 10000010
using namespace std;
int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch-'0'<0||ch-'0'>9){if(ch=='-') f=-1;ch=getchar();}
    while(ch-'0'>=0&&ch-'0'<=9){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n;
int prime[maxn],primesize;
bool isprime[maxn];
void get_prime()
{
    memset(isprime,true,sizeof(isprime));
    isprime[1]=false;
    for(int i=2;i<=maxn-10;i++)
    {
        if(isprime[i])  prime[++primesize]=i;
        for(int j=1;j<=primesize&&i*prime[j]<=maxn-10;j++)
        {
            isprime[i*prime[j]]=false;
            if(i%prime[j]==0)  break;
        }
    }
}
int s[maxn];
int a[101],b[201];
int top1,top2;
int re[101][101];
int match[101];
int vis[101];
bool dfs(int x)
{
    for(int i=1;i<=top2;i++)
    {
        if(re[x][i]&&!vis[i])
        {
            vis[i]=1;
            if(!match[i]||dfs(match[i]))
            {
                match[i]=x;
                return true;
            }
        }
    }
    return false;
}
int main()
{
    get_prime();
    n=read();
    for(int i=1;i<=n;i++)  s[read()]^=1;
    for(int i=1;i<=maxn-9;i++)
    {
        if(s[i]!=s[i-1])
        {
            if(i&1)  a[++top1]=i;
            else     b[++top2]=i;
        }
    }
    for(int i=1;i<=top1;i++)
      for(int j=1;j<=top2;j++)  if(isprime[abs(a[i]-b[j])])  re[i][j]=1;
    int a=0;
    for(int i=1;i<=top1;i++)
    {
        memset(vis,0,sizeof(vis));
        if(dfs(i))  a++;
    }
    printf("%d\n",a+((top1-a)/2)*2+((top2-a)/2)*2+(top1-a)%2*(top2-a)%2*3);
    return 0;
}
```