#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcountll
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC
#define debug(x) std::cout << #x << ": " << x << '\n';

namespace Mag {
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
const int maxn = 505;
typedef vector<int> vi;

// BEGIN_CODE
int n;
vi e[maxn];
int mt[maxn], p[maxn], base[maxn], b[maxn], blos[maxn];
int q[maxn];
int blca[maxn]; // used for lca

void clear() {
    for (int i = 0; i < maxn; ++i)  
        e[i].clear();
    memset(mt, 0, sizeof mt);
    memset(p, 0, sizeof p);
    memset(base, 0, sizeof base);
    memset(b, 0, sizeof b);
    memset(blos, 0, sizeof blos);
    memset(q, 0, sizeof q);
    memset(blca, 0, sizeof blca);
}   

int lca(int u, int v) {
    forn(i, n) blca[i] = 0;
    while (true) {
        u = base[u];
        blca[u] = 1;
        if (mt[u] == -1) break;
        u = p[mt[u]];
    }
    while (!blca[base[v]]) {
        v = p[mt[base[v]]];
    }
    return base[v];
}

void mark_path(int v, int b, int ch) {
    while (base[v] != b) {
        blos[base[v]] = blos[base[mt[v]]] = 1;
        p[v] = ch;
        ch = mt[v];
        v = p[mt[v]];
    }
}

int find_path(int root) {
    forn(i, n) {
        base[i] = i;
        p[i] = -1;
        b[i] = 0;
    }

    b[root] = 1;
    q[0] = root;
    int lq = 0, rq = 1;
    while (lq != rq) {
        int v = q[lq++];
        for (int to: e[v]) {
            if (base[v] == base[to] || mt[v] == to) continue;
            if (to==root || (mt[to] != -1 && p[mt[to]] != -1)) {
                int curbase = lca(v, to);
                forn(i, n) blos[i] = 0;
                mark_path(v, curbase, to);
                mark_path(to, curbase, v);
                forn(i, n) if (blos[base[i]]) {
                    base[i] = curbase;
                    if (!b[i]) b[i] = 1, q[rq++] = i;
                }
            } else if (p[to] == -1) {
                p[to] = v;
                if (mt[to] == -1) {
                    return to;
                }
                to = mt[to];
                b[to] = 1;
                q[rq++] = to;

            }
        }
    }
    return -1;
}

int matching() {
    forn(i, n) mt[i] = -1;
    int res = 0;
    forn(i, n) if (mt[i] == -1) {
        int v = find_path(i);
        if (v != -1) {
            ++res;
            while (v != -1) {
                int pv = p[v], ppv = mt[p[v]];
                mt[v] = pv, mt[pv] = v;
                v = ppv;
            }
        }
    }
    return res;
}
// END_CODE

int match(int n_, int m, vector <ii> ed) {
    clear();

    n = n_;
    for (auto t : ed) {
        e[t.f].app(t.s);
        e[t.s].app(t.f);
    }   
    int res = matching();
    return res;
}

};

const int N = 207;
const int INF = 1e9+7;
const int C = 1e7+7;

bool used[N];

bool p[C];

int get(int a, int b) {
    if (b < a)
        swap(a, b);

    if ((b - a) % 2 == 0)
        return 2;
    else if (p[b-a])
        return 1;
    else
        return 3;
}

int cost[N][N];
int dp[1 << 20];

signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    #define endl '\n'
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    for (int i = 2; i < C; ++i)
        p[i] = 1;
    for (int i = 2; i < C; ++i) 
        if (p[i])
            for (int j = i * 2; j < C; j += i)
                p[j] = 0;

    int n;
    cin >> n;
    map <int, int> d;
    while (n--) {
        int x;
        cin >> x;
        d[x] ^= 1;
        d[x+1] ^= 1;        
    }

    vector <int> c;
    for (auto e : d) {
        if (e.s)
            c.app(e.f);
    }   

    #ifdef HOME
    cout << "C : ";
    for (auto e : c)
        cout << e << ' ';
    cout << endl;
    #endif

    vector <ii> ed;
    for (int i = 0; i < c.size(); ++i) {
        for (int j = i + 1; j < c.size(); ++j) {
            if (get(c[i], c[j]) == 1) {
                ed.app(mp(i+1,j+1));
            }
        }   
    }    

    int ans = Mag::match(c.size()+1, ed.size(), ed);

    #ifdef HOME
    cout << "matching : " << ans << endl;
    #endif

    vector <int> cnt(2);
    for (auto e : c)
        cnt[e&1]++;
    for (int t = 0; t < 2; ++t)
        cnt[t] -= ans;

    for (int t = 0; t < 2; ++t) {
        ans += cnt[t] - (cnt[t]&1);
        cnt[t] &= 1;
    }

    if (cnt[0]) {
        ans += 3;
    }   

    cout << ans << endl;
}

Measured memory_bytes: 13700