#include <bits/stdc++.h>
using namespace std;
const int N = (int)1e7 + 10;
inline int read()
{
  int p=0; int f=1; char ch=getchar();
  while(ch<'0' || ch>'9'){if(ch=='-') f=-1; ch=getchar();}
  while(ch>='0' && ch<='9'){p=p*10+ch-'0'; ch=getchar();}
  return p*f;
}

int prime[N],pri; bool v[N];
void get_prime(int n)
{
  memset(v,1,sizeof(v)); v[0] = v[1] = 0; pri = 0;
  for(int i=2;i<=n;i++)
  {
    if(v[i]) prime[++pri] = i;
    for(int j=1;(j<=pri) && (i*prime[j] <= n);j++)
    {
      v[i*prime[j]] = 0;
      if(i%prime[j]==0) break;
    }
  }
  v[2] = 0;
}

struct node{int x,y,next;}edge[100010]; int len,first[N];
void ins(int x,int y){len++; edge[len].x=x; edge[len].y=y; edge[len].next=first[x]; first[x]=len;}

int n,a[N],b[N];


int chw[N],match[N];
bool dfs(int x)
{
  for(int k=first[x];k!=-1;k=edge[k].next)
  {
    int y=edge[k].y;
    if(!chw[y])
    {
      chw[y] = 1;
      if((match[y] == 0) || dfs(match[y])){match[y] = x; return 1;}
    }
  }
  return 0;
}

int main()
{

  get_prime(1e7+1);

  n = read(); len = 0; memset(first,-1,sizeof(first));
  for(int i=1;i<=n;i++) a[read()] = 1;
  for(int i=1;i<=(int)1e7+1;i++) b[i] = abs(a[i] - a[i-1]);
  for(int i=1;i<=(int)1e7+1;i++) a[i] = b[i];
  int blen = 0; for(int i=1;i<=(int)1e7+1;i++) if(a[i] == 1) b[++blen] = i;
  int c=0,d=0; for(int i=1;i<=blen;i++) if(b[i] & 1) c++; else d++;
  for(int i=1;i<=blen;i++) if(b[i] & 1) for(int j=1;j<=blen;j++) if(!(b[j]&1)) if(v[abs(b[i] - b[j])]) ins(i,j);
  int ans=0; for(int i=1;i<=blen;i++)
  {
    for(int j=1;j<=blen;j++) chw[j] = 0;
    if(dfs(i)) ans++;
  }
 
  c-=ans; d-=ans;
  ans += 2*(c/2 + d/2); c%=2; d%=2;
  if(c && d) ans+=3;

  return printf("%d\n",ans),0;
}
### Prompt

Develop a solution in Cpp 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 <bits/stdc++.h>
using namespace std;
const int N = (int)1e7 + 10;
inline int read()
{
  int p=0; int f=1; char ch=getchar();
  while(ch<'0' || ch>'9'){if(ch=='-') f=-1; ch=getchar();}
  while(ch>='0' && ch<='9'){p=p*10+ch-'0'; ch=getchar();}
  return p*f;
}

int prime[N],pri; bool v[N];
void get_prime(int n)
{
  memset(v,1,sizeof(v)); v[0] = v[1] = 0; pri = 0;
  for(int i=2;i<=n;i++)
  {
    if(v[i]) prime[++pri] = i;
    for(int j=1;(j<=pri) && (i*prime[j] <= n);j++)
    {
      v[i*prime[j]] = 0;
      if(i%prime[j]==0) break;
    }
  }
  v[2] = 0;
}

struct node{int x,y,next;}edge[100010]; int len,first[N];
void ins(int x,int y){len++; edge[len].x=x; edge[len].y=y; edge[len].next=first[x]; first[x]=len;}

int n,a[N],b[N];


int chw[N],match[N];
bool dfs(int x)
{
  for(int k=first[x];k!=-1;k=edge[k].next)
  {
    int y=edge[k].y;
    if(!chw[y])
    {
      chw[y] = 1;
      if((match[y] == 0) || dfs(match[y])){match[y] = x; return 1;}
    }
  }
  return 0;
}

int main()
{

  get_prime(1e7+1);

  n = read(); len = 0; memset(first,-1,sizeof(first));
  for(int i=1;i<=n;i++) a[read()] = 1;
  for(int i=1;i<=(int)1e7+1;i++) b[i] = abs(a[i] - a[i-1]);
  for(int i=1;i<=(int)1e7+1;i++) a[i] = b[i];
  int blen = 0; for(int i=1;i<=(int)1e7+1;i++) if(a[i] == 1) b[++blen] = i;
  int c=0,d=0; for(int i=1;i<=blen;i++) if(b[i] & 1) c++; else d++;
  for(int i=1;i<=blen;i++) if(b[i] & 1) for(int j=1;j<=blen;j++) if(!(b[j]&1)) if(v[abs(b[i] - b[j])]) ins(i,j);
  int ans=0; for(int i=1;i<=blen;i++)
  {
    for(int j=1;j<=blen;j++) chw[j] = 0;
    if(dfs(i)) ans++;
  }
 
  c-=ans; d-=ans;
  ans += 2*(c/2 + d/2); c%=2; d%=2;
  if(c && d) ans+=3;

  return printf("%d\n",ans),0;
}
```