#include <bits/stdc++.h>

#define rep(i,s,n) for(int i = int(s); i < int(n); i++)
#define rrep(i,s,n) for(int i = int(n) - 1; i >= int(s); i--)
#define all(v) (v).begin(), (v).end()

using ll = long long;
using ull = unsigned long long;
using ld = long double;

template<class T>
bool chmin(T &a, T b) {
    if(a <= b) return false;
    a = b;
    return true;
}

template<class T>
bool chmax(T &a, T b) {
    if(a >= b) return false;
    a = b;
    return true;
}

using namespace std;
const int iinf = 1e9;

int main() {
    
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    const int mx = 200100;
    vector<int> ps(mx,1);
    for (int p = 2; p < mx; p++){
        if (ps[p] != 1) continue;
        for (int q = p; q < mx; q += p){
            ps[q] = p;
        }
    }
    int n; cin >> n;
    vector<int> a(n);
    rep(i,0,n) cin >> a[i];
    auto ok = [&](int l, int r, int li, int ri){
        if (l > r){
            swap(l,r);
            swap(li,ri);
        }
        int vl = a[li], vr = a[ri];
        if (l == 0){
            if (r == 0){
                return ps[vl+vr] == vl+vr;
            }
            if (r == 1){
                return ps[vl+1] == vl+1;
            }
            if (r == 2){
                return vl % 2 == 1;
            }
            if (r == 3){
                return vl % 2 == 0;
            }
            return false;
        }
        if (l == 1){
            return r <= 2;
        }
        if (l == 2){
            return r == 3;
        }
        return false;
    };
    vector<vector<int>> dp(n,vector<int>(4,iinf));
    dp[0][0] = 0;
    dp[0][1] = dp[0][2] = dp[0][3] = 1;
    rep(i,1,n){
        rep(l,0,4) rep(r,0,4){
            if (!ok(l,r,i-1,i)) continue;
            chmin(dp[i][r],dp[i-1][l]+(r == 0 ? 0 : 1));
        }
    }
    int ans = iinf;
    rep(i,0,4) chmin(ans,dp[n-1][i]);
    cout << ans << endl;
}