#include<bits/stdc++.h>
using namespace std;
using Int = long long;

struct BiMatch{
  Int n;
  vector<vector<Int> > G;
  vector<Int> match,used;
  
  BiMatch(){}
  BiMatch(Int sz):n(sz),G(sz),match(sz),used(sz){}
  
  void add_edge(Int u,Int v){
    G[u].push_back(v);
    G[v].push_back(u);
  }

  bool dfs(Int v){
    used[v]=true;
    for(Int i=0;i<(Int)G[v].size();i++){
      Int u=G[v][i],w=match[u];
      if(w<0||(!used[w]&&dfs(w))){
	match[v]=u;
	match[u]=v;
	return true;
      }
    }
    return false;
  }

  Int build(){
    Int res=0;
    fill(match.begin(),match.end(),-1);
    for(Int v=0;v<n;v++){
      if(match[v]<0){
	fill(used.begin(),used.end(),0);
	if(dfs(v)){
	  res++;
	}
      }
    }
    return res;
  }
};


Int isprime(Int x){
  if(x<=2) return 0;
  for(Int i=2;i*i<=x;i++)
    if(x%i==0) return 0;
  return 1;
}

//INSERT ABOVE HERE
signed main(){
  Int n;
  cin>>n;
  vector<Int> x(n);
  for(Int i=0;i<n;i++) cin>>x[i];
  
  vector<Int> a(1e7+100,0);
  for(Int i=0;i<n;i++) a[x[i]]=1;
  vector<Int> b;
  for(Int i=1;i<(Int)a.size();i++)
    if(a[i]^a[i-1]) b.emplace_back(i);

  Int m=b.size();
  BiMatch bm(m);
  for(Int i=0;i<m;i++)
    for(Int j=0;j<i;j++)
      if(isprime(b[i]-b[j]))
	bm.add_edge(i,j);

  Int k=bm.build();
  Int o=0,e=0;
  for(Int x:b) if(x&1) o++;else e++;
  //cout<<k<<" "<<o<<" "<<e<<endl;
  Int ans=k+((o-k)/2*2)+((e-k)/2*2)+((o-k)&1?3:0);
  cout<<ans<<endl;
  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
#include<bits/stdc++.h>
using namespace std;
using Int = long long;

struct BiMatch{
  Int n;
  vector<vector<Int> > G;
  vector<Int> match,used;
  
  BiMatch(){}
  BiMatch(Int sz):n(sz),G(sz),match(sz),used(sz){}
  
  void add_edge(Int u,Int v){
    G[u].push_back(v);
    G[v].push_back(u);
  }

  bool dfs(Int v){
    used[v]=true;
    for(Int i=0;i<(Int)G[v].size();i++){
      Int u=G[v][i],w=match[u];
      if(w<0||(!used[w]&&dfs(w))){
	match[v]=u;
	match[u]=v;
	return true;
      }
    }
    return false;
  }

  Int build(){
    Int res=0;
    fill(match.begin(),match.end(),-1);
    for(Int v=0;v<n;v++){
      if(match[v]<0){
	fill(used.begin(),used.end(),0);
	if(dfs(v)){
	  res++;
	}
      }
    }
    return res;
  }
};


Int isprime(Int x){
  if(x<=2) return 0;
  for(Int i=2;i*i<=x;i++)
    if(x%i==0) return 0;
  return 1;
}

//INSERT ABOVE HERE
signed main(){
  Int n;
  cin>>n;
  vector<Int> x(n);
  for(Int i=0;i<n;i++) cin>>x[i];
  
  vector<Int> a(1e7+100,0);
  for(Int i=0;i<n;i++) a[x[i]]=1;
  vector<Int> b;
  for(Int i=1;i<(Int)a.size();i++)
    if(a[i]^a[i-1]) b.emplace_back(i);

  Int m=b.size();
  BiMatch bm(m);
  for(Int i=0;i<m;i++)
    for(Int j=0;j<i;j++)
      if(isprime(b[i]-b[j]))
	bm.add_edge(i,j);

  Int k=bm.build();
  Int o=0,e=0;
  for(Int x:b) if(x&1) o++;else e++;
  //cout<<k<<" "<<o<<" "<<e<<endl;
  Int ans=k+((o-k)/2*2)+((e-k)/2*2)+((o-k)&1?3:0);
  cout<<ans<<endl;
  return 0;
}

```