#include <iostream>
#include <vector>
#include <map>
#include <stack>
using namespace std;

#define REP(i,n) for(int i=0;i<(n);i++)

bool isp(int x){
  if(x<=1)return false;
  if(x==2)return true;
  if(x%2==0)return false;
  for(int y=3;y*y<=x;y+=2){
    if(x%y==0)return false;
  }
  return true;
}

int n;
int x[125];
int cap[252][252];
int main(void){
  scanf("%d",&n);
  REP(i,n)scanf("%d",x+i);
  map<int,int> M;
  REP(i,n){
    M[x[i]] ^= 1;
    M[x[i]+1] ^= 1;
  }
  vector<int> even,odd;
  for(auto P : M)if(P.second==1){
    (P.first%2==0 ? even : odd).push_back(P.first);
  }
  int ne = even.size();
  int no = odd.size();
  n = ne + no + 2;
  int s = ne+no;
  int t = ne+no+1;
  REP(i,ne)cap[s][i] = 1;
  REP(i,no)cap[ne+i][t] = 1;
  REP(i,ne)REP(j,no){
    int d = abs(even[i]-odd[j]);
    if(d<3)continue;
    if(isp(d)){
      cap[i][ne+j] = 1;
    }
  }
  int f = 0;
  while(true){
    vector<int> bef(n,-1);
    vector<bool> vstd(n,false);
    stack<int> S;
    S.push(s);
    vstd[s] = true;
    while(S.size()){
      int p = S.top(); S.pop();
      if(p==t)break;
      REP(i,n)if(cap[p][i] && !vstd[i]){
        vstd[i] = true;
        bef[i] = p;
        S.push(i);
      }
    }
    if(bef[t]==-1)break;
    f++;
    int cur = t;
    while(true){
      int nxt = bef[cur];
      if(nxt==-1)break;
      cap[nxt][cur] = 0;
      cap[cur][nxt] = 1;
      cur = nxt;
    }
  }
  int ans = 0;
  ans += f;
  ans += (ne-f);
  ans += (no-f);
  if((ne-f)%2==1)ans++;
  printf("%d\n",ans);
}

### 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
#include <iostream>
#include <vector>
#include <map>
#include <stack>
using namespace std;

#define REP(i,n) for(int i=0;i<(n);i++)

bool isp(int x){
  if(x<=1)return false;
  if(x==2)return true;
  if(x%2==0)return false;
  for(int y=3;y*y<=x;y+=2){
    if(x%y==0)return false;
  }
  return true;
}

int n;
int x[125];
int cap[252][252];
int main(void){
  scanf("%d",&n);
  REP(i,n)scanf("%d",x+i);
  map<int,int> M;
  REP(i,n){
    M[x[i]] ^= 1;
    M[x[i]+1] ^= 1;
  }
  vector<int> even,odd;
  for(auto P : M)if(P.second==1){
    (P.first%2==0 ? even : odd).push_back(P.first);
  }
  int ne = even.size();
  int no = odd.size();
  n = ne + no + 2;
  int s = ne+no;
  int t = ne+no+1;
  REP(i,ne)cap[s][i] = 1;
  REP(i,no)cap[ne+i][t] = 1;
  REP(i,ne)REP(j,no){
    int d = abs(even[i]-odd[j]);
    if(d<3)continue;
    if(isp(d)){
      cap[i][ne+j] = 1;
    }
  }
  int f = 0;
  while(true){
    vector<int> bef(n,-1);
    vector<bool> vstd(n,false);
    stack<int> S;
    S.push(s);
    vstd[s] = true;
    while(S.size()){
      int p = S.top(); S.pop();
      if(p==t)break;
      REP(i,n)if(cap[p][i] && !vstd[i]){
        vstd[i] = true;
        bef[i] = p;
        S.push(i);
      }
    }
    if(bef[t]==-1)break;
    f++;
    int cur = t;
    while(true){
      int nxt = bef[cur];
      if(nxt==-1)break;
      cap[nxt][cur] = 0;
      cap[cur][nxt] = 1;
      cur = nxt;
    }
  }
  int ans = 0;
  ans += f;
  ans += (ne-f);
  ans += (no-f);
  if((ne-f)%2==1)ans++;
  printf("%d\n",ans);
}

```