#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define F first
#define S second
#define int long long
#define ll long long
//#define int  unsigned long long
#define pb push_back
//#define double long double

using namespace std;
using namespace __gnu_pbds;
typedef  tree< int , null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int mod = 1e9 + 7;
const int N = 1000;
struct Edge {
    int from, to, f, c, w;
};
vector < Edge >  edges;
vector < int > g[N];
int n, d[N], f[N], b[N][N];
int p[N];
void add(int a, int b, int c, int w){
    Edge e;
    e.from = a; e.to = b; e.c = c; e.w = w; e.f = 0;
    edges.pb(e);
  //  cout << a << " " << b << " " << c << " " << w << endl;
    g[a].pb(edges.size() - 1);
    e.w = -e.w; e.c = 0; swap(e.from, e.to);
    edges.pb(e);
    g[b].pb(edges.size() - 1);
}
bool spfa(int s, int t){
    for (int i = 1; i < N; i++){
        d[i] = 1e9;
        f[i] = 0;
    }
    queue < int > q;
    q.push(s);
    d[s] = 0;
    f[s] = 1;
    while(!q.empty()){
        int v = q.front();
        q.pop();
        f[v] = 0;
        for (int i = 0; i < g[v].size(); i++){
            Edge e = edges[g[v][i]];
            if (e.f < e.c && d[e.to] > d[v] + e.w){
                p[e.to] = g[v][i];
                d[e.to] = d[v] + e.w;
                if (!f[e.to])
                    q.push(e.to);
                f[e.to] = 1;
            }
        }
    }
    return d[t] != 1e9;
}
int flow(int s, int t){
    int cost = 0;
    while(spfa(s, t)){
        int v = t;
        while(v != s && v != 0){
            auto k = p[v];
            edges[k].f++;
            edges[k ^ 1].f--;
            cost += edges[k].w;
            v = edges[k].from;
        }
    }
    return cost;
}
int mx[N], mn[N];
int ff(int x){
    if (x == 2) return 2;
    if (x == 1) return 3;
    int pr = 1;
    for (int i = 2; i * i <= x; i++){
        if (x % i == 0) pr = 0;
    }
    if (pr) return 1;
    return 2 + (x % 2);
}
int usedd[N];
vector < int > gr[N];
void dfss(int v){
    usedd[v] = 1;
    for (auto u: gr[v]){
        if (usedd[u]) continue;
        dfss(u);
    }
}
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("input.txt", "r", stdin);
    cin >> n;
    int p = -1;
    vector < int > a;
    for (int i = 1; i <= n; i++){
        int x;
        cin >> x;
        if (x != p + 1){
            if (p != -1) a.pb(p + 1);
            a.pb(x);
        }
        p = x;
    }
    a.pb(p + 1);
    n = a.size();
    int cnt = 0;
    for (int i = 0; i < a.size(); i++){
        add(2 * n + 1, i + 1, 1, 0);
        add(n + i + 1, 2 * n + 2, 1, 0);
        if (a[i] % 2) cnt++;
        for (int j = i + 1; j < a.size(); j++){
            if (i == j) continue;
            int x = a[i];
            int y = a[j];
            if (ff(abs(x - y)) == 1){
                if (x % 2 == 0)
                add(i + 1, n + j + 1, 1, 1); else
                add(j + 1, n + i + 1, 1, 1);
            }
            if (ff(abs(x - y)) != 3){
                gr[i + 1].pb(j + 1);
                gr[j + 1].pb(i + 1);
            }
        }
    }
    n = 2 * n + 2;
    int ans = flow(n - 1, n);
    dfss(1);
    int k = 0;
    n = (n - 2) / 2;
    if ((cnt - ans) % 2){
        ans = ans + (n - 2 * ans) + 1;
    } else{
        ans = ans + (n - 2 * ans);
    }
    cout << ans;
}


Measured memory_bytes: 1372