#include <bits/stdc++.h>
const int N=1e7+10;
using namespace std;
inline int gi(){
  char ch=getchar();int x=0,q=0;
  while(ch<'0' || ch>'9') ch=='-'?q=1:0,ch=getchar();
  while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
  return q?(-x):x;
}
int mark[N],pri[N],tot,P=1e7+1,n,m,g[N];
int c[105][105],bl[105],vis[105],a[105],b[105];
void pre(){
  for (int i=2,s; i<=P; ++i){
    if (!mark[i]) pri[++tot]=i;
    for (int j=1; j<=tot&&(s=i*pri[j])<=P; ++j){
      mark[s]=1;
      if (i%pri[j]==0) break;
    }
  }
  return;
}
int dfs(int x){
  for (int i=1; i<=m; ++i)
    if (c[x][i]&&!vis[i]){
      vis[i]=1;
      if (!bl[i]||dfs(bl[i]))
	return bl[i]=x;
    }
  return 0;
}
int main(){
  int p=gi(),s;
  pre();
  for (int i=1; i<=p; ++i)
    g[gi()]=1;
  for (int i=P; i>=1; --i)
    g[i]^=g[i-1];
  for (int i=1; i<=P; ++i)
    if (g[i]){
      if (i&1) a[++n]=i;
      else b[++m]=i;
    }
  for (int i=1; i<=n; ++i)
    for (int j=1; j<=m; ++j){
      s=abs(a[i]-b[j]);
      if (s!=1&&!mark[s])
	c[i][j]=1;
    }
  int ans=0;
  for (int i=1; i<=n; ++i){
    memset(vis,0,sizeof(vis));
    if (dfs(i)) ++ans;
  }
  cout<<ans+(n-ans)/2*2+(m-ans)/2*2+(((n-ans)&1)||((m-ans)&1))*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
#include <bits/stdc++.h>
const int N=1e7+10;
using namespace std;
inline int gi(){
  char ch=getchar();int x=0,q=0;
  while(ch<'0' || ch>'9') ch=='-'?q=1:0,ch=getchar();
  while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
  return q?(-x):x;
}
int mark[N],pri[N],tot,P=1e7+1,n,m,g[N];
int c[105][105],bl[105],vis[105],a[105],b[105];
void pre(){
  for (int i=2,s; i<=P; ++i){
    if (!mark[i]) pri[++tot]=i;
    for (int j=1; j<=tot&&(s=i*pri[j])<=P; ++j){
      mark[s]=1;
      if (i%pri[j]==0) break;
    }
  }
  return;
}
int dfs(int x){
  for (int i=1; i<=m; ++i)
    if (c[x][i]&&!vis[i]){
      vis[i]=1;
      if (!bl[i]||dfs(bl[i]))
	return bl[i]=x;
    }
  return 0;
}
int main(){
  int p=gi(),s;
  pre();
  for (int i=1; i<=p; ++i)
    g[gi()]=1;
  for (int i=P; i>=1; --i)
    g[i]^=g[i-1];
  for (int i=1; i<=P; ++i)
    if (g[i]){
      if (i&1) a[++n]=i;
      else b[++m]=i;
    }
  for (int i=1; i<=n; ++i)
    for (int j=1; j<=m; ++j){
      s=abs(a[i]-b[j]);
      if (s!=1&&!mark[s])
	c[i][j]=1;
    }
  int ans=0;
  for (int i=1; i<=n; ++i){
    memset(vis,0,sizeof(vis));
    if (dfs(i)) ++ans;
  }
  cout<<ans+(n-ans)/2*2+(m-ans)/2*2+(((n-ans)&1)||((m-ans)&1))*3;
  return 0;
}

```