#include <bits/stdc++.h>

using namespace std; 

const int maxn = 1e7 + 1; 

int n, a[505], G[505][505], col[maxn + 5]; 
int p[maxn + 5], flag[maxn + 5], tot, cnt, mat[205], vis[205];  

int dfs(int u) {
    for (int v = 1; v <= cnt; v++) {
        if (!(a[v] & 1) && !vis[v] && G[u][v]) {
            vis[v] = 1; 
            if (!mat[v] or dfs(mat[v])) {
                mat[v] = u; 
                return 1; 
            }
        }
    }
    return 0; 
}

int main() {
    scanf("%d", &n); 
    for (int i = 1; i <= n; i++) {
        int t; 
        scanf("%d", &t); 
        col[t] = 1;  
    }
    flag[1] = 1; 
    if (col[1] != col[0]) a[++cnt] = 1; 
    for (int i = 2; i <= maxn; i++) {
        if (col[i] != col[i - 1]) a[++cnt] = i; 
        if (!flag[i]) {
            p[++tot] = i; 
        }
        for (int j = 1; j <= tot && i * p[j] <= maxn; j++) {
            flag[i * p[j]] = 1; 
            if (i % p[j] == 0) break ; 
        }
    }
    flag[2] = 1;
    for (int i = 1; i <= cnt; i++) {
        for (int j = i + 1; j <= cnt; j++) {
            if (!flag[abs(a[j] - a[i])]) {
                G[i][j] = G[j][i] = 1; 
            }
        }
    }
    int mx = 0, odd = 0, even; 
    for (int i = 1; i <= cnt; i++) {
        if (a[i] & 1) {
            memset(vis, 0, sizeof(vis)); 
            if (dfs(i)) mx++; 
            odd++; 
        }
    }
    even = cnt - odd; 
    odd -= mx, even -= mx; 
    int ans = mx; 
    if (odd & 1) {
        ans += odd - 1 + even - 1 + 3; 
    }
    else {
        ans += odd + even; 
    }
    cout << ans << '\n'; 
    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; 

const int maxn = 1e7 + 1; 

int n, a[505], G[505][505], col[maxn + 5]; 
int p[maxn + 5], flag[maxn + 5], tot, cnt, mat[205], vis[205];  

int dfs(int u) {
    for (int v = 1; v <= cnt; v++) {
        if (!(a[v] & 1) && !vis[v] && G[u][v]) {
            vis[v] = 1; 
            if (!mat[v] or dfs(mat[v])) {
                mat[v] = u; 
                return 1; 
            }
        }
    }
    return 0; 
}

int main() {
    scanf("%d", &n); 
    for (int i = 1; i <= n; i++) {
        int t; 
        scanf("%d", &t); 
        col[t] = 1;  
    }
    flag[1] = 1; 
    if (col[1] != col[0]) a[++cnt] = 1; 
    for (int i = 2; i <= maxn; i++) {
        if (col[i] != col[i - 1]) a[++cnt] = i; 
        if (!flag[i]) {
            p[++tot] = i; 
        }
        for (int j = 1; j <= tot && i * p[j] <= maxn; j++) {
            flag[i * p[j]] = 1; 
            if (i % p[j] == 0) break ; 
        }
    }
    flag[2] = 1;
    for (int i = 1; i <= cnt; i++) {
        for (int j = i + 1; j <= cnt; j++) {
            if (!flag[abs(a[j] - a[i])]) {
                G[i][j] = G[j][i] = 1; 
            }
        }
    }
    int mx = 0, odd = 0, even; 
    for (int i = 1; i <= cnt; i++) {
        if (a[i] & 1) {
            memset(vis, 0, sizeof(vis)); 
            if (dfs(i)) mx++; 
            odd++; 
        }
    }
    even = cnt - odd; 
    odd -= mx, even -= mx; 
    int ans = mx; 
    if (odd & 1) {
        ans += odd - 1 + even - 1 + 3; 
    }
    else {
        ans += odd + even; 
    }
    cout << ans << '\n'; 
    return 0; 
}
```