#include <bits/stdc++.h>


using namespace std;

using ll = long long;
using ld = long double;

#define mp make_pair

const int p = 998244353;


int mul(int a, int b) {
    return (1LL * a * b) % p;
}

int add(int a, int b) {
    int s = (a+b);
    if (s>=p) s-=p;
    return s;
}

int sub(int a, int b) {
    int s = (a+p-b);
    if (s>=p) s-=p;
    return s;
}

int po(int a, int deg)
{
    if (deg==0) return 1;
    if (deg%2==1) return mul(a, po(a, deg-1));
    int t = po(a, deg/2);
    return mul(t, t);
}

int inv(int n)
{
    return po(n, p-2);
}

/*struct DSU {
    vector<int> sz;
    vector<int> parent;

    void make_set(int v) {
        parent[v] = v;
        sz[v] = 1;
    }

    int find_set(int v) {
        if (v == parent[v])
            return v;
        return parent[v] = find_set(parent[v]);
    }

    void union_sets(int a, int b) {
        a = find_set(a);
        b = find_set(b);
        if (a != b) {
            if (sz[a] < sz[b])
                swap(a, b);
            parent[b] = a;
            sz[a] += sz[b];
        }
    }

    DSU(int n) {
        sz.resize(n);
        parent.resize(n);
        for (int i = 0; i < n; i++) make_set(i);
    }
};*/

/*const int N = 1200000;

vector<int> facs(N), invfacs(N);

void init()
{
    facs[0] = 1;
    for (int i = 1; i<N; i++) facs[i] = mul(facs[i-1], i);
    invfacs[N-1] = inv(facs[N-1]);
    for (int i = N-2; i>=0; i--) invfacs[i] = mul(invfacs[i+1], i+1);
}

int C(int n, int k)
{
    return mul(facs[n], mul(invfacs[k], invfacs[n-k]));
}*/

/*const int N = 1e9;

struct MinSegTree
{
    int n;
    vector<int> t;

    void build(vector<int> &a, int v, int tl, int tr) {
        if (tl == tr) {
            t[v] = a[tl];
        } else {
            int tm = (tl + tr) / 2;
            build(a, v*2, tl, tm);
            build(a, v*2+1, tm+1, tr);
            t[v] = min(t[v*2], t[v*2+1]);
        }
    }

    int minn(int v, int tl, int tr, int l, int r) {
        if (l > r)
            return N;
        if (l == tl && r == tr) {
            return t[v];
        }
        int tm = (tl + tr) / 2;
        return min(minn(v*2, tl, tm, l, min(r, tm)), minn(v*2+1, tm+1, tr, max(l, tm+1), r));
    }

    MinSegTree(vector<int> &a)
    {
        n = a.size();
        t.resize(4*n);
        build(a, 1, 0, n-1);
    }

};*/


template<int V, class T=long long>
class max_flow {
    static const T INF = numeric_limits<T>::max();

    unordered_map<int, T> cap[V];
    int dist[V];
    bool blocked[V];

    void bfs(int s) {
        memset(dist, -1, sizeof dist);
        dist[s] = 0;
        queue<int> q;
        q.push(s);
        while (!q.empty()) {
            int n = q.front();
            q.pop();
            for (auto p : cap[n]) {
                if (p.second && dist[p.first] == -1) {
                    dist[p.first] = dist[n] + 1;
                    q.push(p.first);
                }
            }
        }
    }

    T augment(int n, T amt, int t) {
        if (n == t) return amt;
        if (blocked[n]) return 0;
        T remaining = amt;
        for (auto p : cap[n]) {
            if (dist[p.first] != dist[n] + 1) continue;
            T flowpart = min(remaining, cap[n][p.first]);
            if (flowpart) {
                T cur = augment(p.first, flowpart, t);
                remaining -= cur;
                cap[n][p.first] -= cur;
                cap[p.first][n] += cur;
            }
        }
        if (remaining) blocked[n] = true;
        return amt - remaining;
    }

public:
    void add(int u, int v, T f=1) {
        cap[u][v] += f;
    }

    T calc(int s, int t) {
        T ans = 0;
        while (true) {
            bfs(s);
            memset(blocked, false, sizeof blocked);
            T aug = augment(s, INF, t);
            if (!aug) break;
            ans += aug;
        }
        return ans;
    }

    void clear() {
        for (int i = 0; i < V; i++) {
            cap[i].clear();
        }
    }
};


const int N = 1e7 + 100;

//set<int> primes;
vector<bool> check(N);

void init()
{
    check[1] = true;
    for (int i = 2; i<N; i++) if (!check[i])
    {
        for (int j = 2*i; j<N; j+=i) check[j] = true;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);

    init();

    int n;
    cin>>n;
    vector<int> x(n);
    for (int i = 0; i<n; i++) cin>>x[i];
    set<int> even, odd;
    for (int i = 0; i<n; i++)
    {
        int l = x[i]-1;
        int r = x[i];
        if (l%2) swap(l, r);
        if (even.count(l)) even.erase(l); else even.insert(l);
        if (odd.count(r)) odd.erase(r); else odd.insert(r);
    }

    int E = even.size();
    int O = odd.size();

    vector<int> e(even.begin(), even.end()); vector<int> o(odd.begin(), odd.end());


    max_flow<300> network;

    for (int i = 0; i<E; i++) network.add(0, i+1, 1);
    for (int i = 0; i<O; i++) network.add(1 + E + i, E + O + 1, 1);

    for (int i = 0; i<E; i++)
        for (int j = 0; j<O; j++) if (!check[abs(e[i] - o[j])])
        {
            network.add(i + 1, 1 + E + j, 1);
        }

    int match = network.calc(0, E + O + 1);

    E-=match; O-=match;

    if (E%2==0) cout<<match + E + O;
    else cout<<match + E + O + 1;

}



Measured memory_bytes: 1792