#include <bits/stdc++.h>

using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;

#define FOR(i, a, b) for (int i=a; i<b; i++)
#define F0R(i, a) for (int i=0; i<a; i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
 
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound

const int MOD = 1000000007;
double PI = 4*atan(1);

int N, pre[202], visit[202];
vi x, y[2];
set<int> adj[202];

bool oddprime(int x) {
    x = abs(x);
    if (x <= 2) return 0;
    for (int i = 2; i*i <= x; ++i) if (x % i == 0) return 0;
    return 1;
}

int calc(int flow) {
    return flow+2*((y[0].size()-flow)/2+(y[1].size()-flow)/2)+3*((y[0].size()-flow)%2);    
}

void dfs(int x) {
    visit[x] = 1;
    for (int i: adj[x]) if (!visit[i]) {
        if (visit[201]) break;
        pre[i] = x;
        dfs(i);
    }
}

void backtrack(int x) {
    if (x == 0) return;
    int x1 = pre[x];
    adj[x1].erase(x);
    adj[x].insert(x1);
    backtrack(x1);
}

int main() {
    cin >> N; x.resize(N); 
    F0R(i,N) cin >> x[i];
    F0R(i,N) {
        if (i == 0 || x[i-1]+1 != x[i]) y[(x[i]-1)%2].pb(x[i]-1);
        if (i == N-1 || x[i]+1 != x[i+1]) y[x[i]%2].pb(x[i]);
    }
    
    F0R(i,y[0].size()) adj[0].insert(i+1);
    F0R(i,y[1].size()) adj[i+y[0].size()+1].insert(201);
    F0R(i,y[0].size()) F0R(j,y[1].size()) 
        if (oddprime(y[0][i]-y[1][j])) adj[i+1].insert(j+1+y[0].size());
        
    int flow = 0;
    while (1) {
        memset(visit,0,sizeof visit);
        dfs(0);
        if (!visit[201]) {
            cout << calc(flow);
            return 0;
        }
        flow++;
        backtrack(201);
    }
}
### Prompt

Please formulate 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;
 
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;

#define FOR(i, a, b) for (int i=a; i<b; i++)
#define F0R(i, a) for (int i=0; i<a; i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
 
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound

const int MOD = 1000000007;
double PI = 4*atan(1);

int N, pre[202], visit[202];
vi x, y[2];
set<int> adj[202];

bool oddprime(int x) {
    x = abs(x);
    if (x <= 2) return 0;
    for (int i = 2; i*i <= x; ++i) if (x % i == 0) return 0;
    return 1;
}

int calc(int flow) {
    return flow+2*((y[0].size()-flow)/2+(y[1].size()-flow)/2)+3*((y[0].size()-flow)%2);    
}

void dfs(int x) {
    visit[x] = 1;
    for (int i: adj[x]) if (!visit[i]) {
        if (visit[201]) break;
        pre[i] = x;
        dfs(i);
    }
}

void backtrack(int x) {
    if (x == 0) return;
    int x1 = pre[x];
    adj[x1].erase(x);
    adj[x].insert(x1);
    backtrack(x1);
}

int main() {
    cin >> N; x.resize(N); 
    F0R(i,N) cin >> x[i];
    F0R(i,N) {
        if (i == 0 || x[i-1]+1 != x[i]) y[(x[i]-1)%2].pb(x[i]-1);
        if (i == N-1 || x[i]+1 != x[i+1]) y[x[i]%2].pb(x[i]);
    }
    
    F0R(i,y[0].size()) adj[0].insert(i+1);
    F0R(i,y[1].size()) adj[i+y[0].size()+1].insert(201);
    F0R(i,y[0].size()) F0R(j,y[1].size()) 
        if (oddprime(y[0][i]-y[1][j])) adj[i+1].insert(j+1+y[0].size());
        
    int flow = 0;
    while (1) {
        memset(visit,0,sizeof visit);
        dfs(0);
        if (!visit[201]) {
            cout << calc(flow);
            return 0;
        }
        flow++;
        backtrack(201);
    }
}
```