#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn=10000000;

int prime[2000005];
bool check[maxn+5];

void pre() {
  check[1]=1;
  int tot=0;
  for(int i=2;i<=maxn;i++) {
  	if (!check[i]) prime[++tot]=i;
  	for(int j=1;j<=tot&&i*prime[j]<=maxn;j++) {
  	  check[i*prime[j]]=1;
  	  if (i%prime[j]==0) break;
    }
  }
}

bool in[maxn+5];
int num1[105],num2[105],s1,s2;
bool e[105][105];

bool vis[105];
int link[105];

bool dfs(int x) {
  for(int i=1;i<=s2;i++)
    if (e[x][i]&&!vis[i]) {
    	vis[i]=1;
    	if (!link[i]||dfs(link[i])) {
    		link[i]=x;
    		return 1;
		}
	}
  return 0;
}

int match() {
  int ans=0;
  for(int i=1;i<=s1;i++) {
  	memset(vis,0,sizeof(vis));
  	ans+=dfs(i);
  }
  return ans;
}

int main() {
  pre();
  int n;
  scanf("%d",&n);
  for(int i=1;i<=n;i++) {
  	int x;
  	scanf("%d",&x);
  	in[x]^=1;
  }
  for(int i=1;i<=maxn+2;i++)
    if (in[i]!=in[i-1]) {
    	if (i&1) num1[++s1]=i;
    	else num2[++s2]=i;
	}
  for(int i=1;i<=s1;i++)
    for(int j=1;j<=s2;j++)
      if (!check[abs(num1[i]-num2[j])]) e[i][j]=1;
  int sum=match(); 
  printf("%d\n",sum+((s1-sum)>>1<<1)+((s2-sum)>>1<<1)+((s1-sum)&1)*3);
  return 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 <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn=10000000;

int prime[2000005];
bool check[maxn+5];

void pre() {
  check[1]=1;
  int tot=0;
  for(int i=2;i<=maxn;i++) {
  	if (!check[i]) prime[++tot]=i;
  	for(int j=1;j<=tot&&i*prime[j]<=maxn;j++) {
  	  check[i*prime[j]]=1;
  	  if (i%prime[j]==0) break;
    }
  }
}

bool in[maxn+5];
int num1[105],num2[105],s1,s2;
bool e[105][105];

bool vis[105];
int link[105];

bool dfs(int x) {
  for(int i=1;i<=s2;i++)
    if (e[x][i]&&!vis[i]) {
    	vis[i]=1;
    	if (!link[i]||dfs(link[i])) {
    		link[i]=x;
    		return 1;
		}
	}
  return 0;
}

int match() {
  int ans=0;
  for(int i=1;i<=s1;i++) {
  	memset(vis,0,sizeof(vis));
  	ans+=dfs(i);
  }
  return ans;
}

int main() {
  pre();
  int n;
  scanf("%d",&n);
  for(int i=1;i<=n;i++) {
  	int x;
  	scanf("%d",&x);
  	in[x]^=1;
  }
  for(int i=1;i<=maxn+2;i++)
    if (in[i]!=in[i-1]) {
    	if (i&1) num1[++s1]=i;
    	else num2[++s2]=i;
	}
  for(int i=1;i<=s1;i++)
    for(int j=1;j<=s2;j++)
      if (!check[abs(num1[i]-num2[j])]) e[i][j]=1;
  int sum=match(); 
  printf("%d\n",sum+((s1-sum)>>1<<1)+((s2-sum)>>1<<1)+((s1-sum)&1)*3);
  return 0;
}
```