#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

#define ri register int
#define ssd 10000010
#define sid 205

int n, N = 1e7;
int pr[ssd / 10], tot;
int nj, no, js[sid], os[sid];
bool nop[ssd], e[ssd];

int tim, vis[sid], mat[sid];
bool ex[sid][sid];

inline void Init() {
    for(ri i = 2; i <= N + 1; i ++) {
        if(!nop[i]) pr[++ tot] = i;
        for(ri j = 1; j <= tot; j ++) {
            int nx = i * pr[j]; if(nx > N + 1) break;
            nop[nx] = 1; if(i % pr[j] == 0) break;
        }
    }
    nop[1] = nop[2] = 1;
}

inline int dfs(int o) {
    for(int i = 1; i <= no; i ++)
    if(ex[o][i] && vis[i] != tim) {
        vis[i] = tim;
        if(!mat[i] || dfs(mat[i])) 
        return mat[i] = o, 1;
    }
    return 0;
}

int main() {
    Init();
    cin >> n;
    for(ri i = 1; i <= n; i ++) { int x; cin >> x; e[x] = 1; }
    
    for(ri i = 1; i <= N + 1; i ++)
    if(e[i] != e[i - 1]) {
        if(i & 1) js[++ nj] = i;
        else os[++ no] = i;
    }

    for(ri i = 1; i <= nj; i ++)
    for(ri j = 1; j <= no; j ++)
    if(!nop[abs(js[i] - os[j])]) ex[i][j] = 1;

    int num = 0, ans = 0;

    for(ri i = 1; i <= nj; i ++)
    ++ tim, num += dfs(i);

    nj -= num; no -= num;
    ans = num + nj / 2 * 2 + no / 2 * 2 + (nj & 1) * 3;
    printf("%d\n", ans);
    return 0;
}
### Prompt

Please provide a cpp coded solution 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 <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

#define ri register int
#define ssd 10000010
#define sid 205

int n, N = 1e7;
int pr[ssd / 10], tot;
int nj, no, js[sid], os[sid];
bool nop[ssd], e[ssd];

int tim, vis[sid], mat[sid];
bool ex[sid][sid];

inline void Init() {
    for(ri i = 2; i <= N + 1; i ++) {
        if(!nop[i]) pr[++ tot] = i;
        for(ri j = 1; j <= tot; j ++) {
            int nx = i * pr[j]; if(nx > N + 1) break;
            nop[nx] = 1; if(i % pr[j] == 0) break;
        }
    }
    nop[1] = nop[2] = 1;
}

inline int dfs(int o) {
    for(int i = 1; i <= no; i ++)
    if(ex[o][i] && vis[i] != tim) {
        vis[i] = tim;
        if(!mat[i] || dfs(mat[i])) 
        return mat[i] = o, 1;
    }
    return 0;
}

int main() {
    Init();
    cin >> n;
    for(ri i = 1; i <= n; i ++) { int x; cin >> x; e[x] = 1; }
    
    for(ri i = 1; i <= N + 1; i ++)
    if(e[i] != e[i - 1]) {
        if(i & 1) js[++ nj] = i;
        else os[++ no] = i;
    }

    for(ri i = 1; i <= nj; i ++)
    for(ri j = 1; j <= no; j ++)
    if(!nop[abs(js[i] - os[j])]) ex[i][j] = 1;

    int num = 0, ans = 0;

    for(ri i = 1; i <= nj; i ++)
    ++ tim, num += dfs(i);

    nj -= num; no -= num;
    ans = num + nj / 2 * 2 + no / 2 * 2 + (nj & 1) * 3;
    printf("%d\n", ans);
    return 0;
}
```