#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;
#define INF (1 << 29)
bool prime(int x){
  if(x == 1)return false;
  for(int i = 2;i * i <= x;i++){
    if(x % i == 0)return false;
  }
  return true;
}

int edge[300][300];

int n, x;
map<int, int> cnt;
vector<int> odd, even;

void add_edge(int u, int v, int f){
  edge[u][v] = f;
}


bool come[300];
int flow(int s, int t){
  if(come[s])return 0;
  come[s] = true;
  if(s == t)return 1;
  for(int i = 0;i < 300;i++){
    if(edge[s][i] == 0)continue;
    if(flow(i, t)){
      edge[s][i]--;
      edge[i][s]++;
      return 1;
    }
  }
  return 0;
}

int max_flow(int s, int t){
  int res = 0;
  while(flow(s, t)){
    res++;
    for(int i = 0;i < 300;i++)come[i] = false;
  }
  return res;
}


int main(){
  cin >> n;
  for(int i = 0;i < n;i++){
    cin >> x;
    cnt[x]^=1;
    cnt[x-1]^=1;
  }
  map<int, int>::iterator it;
  for(it = cnt.begin();it != cnt.end();it++){
    if(it->second == 0)continue;
    x = it->first;
    if(x % 2 == 0)even.push_back(x);
    if(x % 2 == 1)odd.push_back(x);
  }
  int s = even.size() + odd.size() + 1;
  int t = s + 1;
  for(int i = 0;i < even.size();i++)add_edge(s, i, 1);
  for(int i = 0;i < odd.size();i++)add_edge(even.size() + i, t, 1);
  
  for(int i = 0;i < even.size();i++){
    for(int j = 0;j < odd.size();j++){
      int dif = abs(even[i] - odd[j]);
      if(prime(dif))add_edge(i, even.size() + j, 1);
    }
  }

  int mxf = max_flow(s, t);
  cout << mxf + (even.size() - mxf) / 2 * 2 + (odd.size() - mxf) / 2 * 2 + (even.size() - mxf) % 2 * 3 << endl;
  return 0;
}
### Prompt

Generate 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<algorithm>
#include<map>
#include<vector>
using namespace std;
#define INF (1 << 29)
bool prime(int x){
  if(x == 1)return false;
  for(int i = 2;i * i <= x;i++){
    if(x % i == 0)return false;
  }
  return true;
}

int edge[300][300];

int n, x;
map<int, int> cnt;
vector<int> odd, even;

void add_edge(int u, int v, int f){
  edge[u][v] = f;
}


bool come[300];
int flow(int s, int t){
  if(come[s])return 0;
  come[s] = true;
  if(s == t)return 1;
  for(int i = 0;i < 300;i++){
    if(edge[s][i] == 0)continue;
    if(flow(i, t)){
      edge[s][i]--;
      edge[i][s]++;
      return 1;
    }
  }
  return 0;
}

int max_flow(int s, int t){
  int res = 0;
  while(flow(s, t)){
    res++;
    for(int i = 0;i < 300;i++)come[i] = false;
  }
  return res;
}


int main(){
  cin >> n;
  for(int i = 0;i < n;i++){
    cin >> x;
    cnt[x]^=1;
    cnt[x-1]^=1;
  }
  map<int, int>::iterator it;
  for(it = cnt.begin();it != cnt.end();it++){
    if(it->second == 0)continue;
    x = it->first;
    if(x % 2 == 0)even.push_back(x);
    if(x % 2 == 1)odd.push_back(x);
  }
  int s = even.size() + odd.size() + 1;
  int t = s + 1;
  for(int i = 0;i < even.size();i++)add_edge(s, i, 1);
  for(int i = 0;i < odd.size();i++)add_edge(even.size() + i, t, 1);
  
  for(int i = 0;i < even.size();i++){
    for(int j = 0;j < odd.size();j++){
      int dif = abs(even[i] - odd[j]);
      if(prime(dif))add_edge(i, even.size() + j, 1);
    }
  }

  int mxf = max_flow(s, t);
  cout << mxf + (even.size() - mxf) / 2 * 2 + (odd.size() - mxf) / 2 * 2 + (even.size() - mxf) % 2 * 3 << endl;
  return 0;
}
```