#include<bits/stdc++.h>
#define fore(i,l,r)	for(int i=(int)(l);i<(int)(r);++i)
#define fi first
#define se second
#define endl '\n'
#define ull unsigned long long
#define ALL(v) v.begin(), v.end()
#define Debug(x, ed) std::cerr << #x << " = " << x << ed;

const int INF=0x3f3f3f3f;
const long long INFLL=1e18;

typedef long long ll;

std::vector<int> minp;
std::vector<int> primes;

void sieve(int n){
    minp.assign(n + 5, 0);
    primes.clear();

    fore(i, 2, n + 1){
        if(!minp[i]){
            minp[i] = i;
            primes.push_back(i);
        }
        for(auto p : primes){
            if(p * i > n) break;
            minp[i * p] = p;
            if(minp[i] == p) break;
        }
    }
}

bool isPrime(int x){
    return x == minp[x];
}

const int N = 100005;

int dp[N][4];

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int n;
    std::cin >> n;
    std::vector<int> a(n + 1);
    fore(i, 1, n + 1) std::cin >> a[i];
    fore(i, 1, n + 1)
        fore(j, 0, 4)
            dp[i][j] = INF;
    
    sieve(2 * N);

    dp[1][0] = 0;
    dp[1][1] = (a[1] != 1);
    dp[1][2] = 1;
    dp[1][3] = 1;

    fore(i, 2, n + 1){
        if(isPrime(a[i - 1] + a[i])) dp[i][0] = dp[i - 1][0];
        if(a[i] & 1){
            dp[i][0] = std::min(dp[i][0], dp[i - 1][2]);
        }
        else{
            dp[i][0] = std::min(dp[i][0], dp[i - 1][3]);
            if(isPrime(1 + a[i])) dp[i][0] = std::min(dp[i][0], dp[i - 1][1]);
        }

        dp[i][1] = dp[i - 1][1] + (a[i] != 1);
        dp[i][1] = std::min({dp[i][1], dp[i - 1][2] + (a[i] != 1)});
        if(a[i - 1] & 1){
            dp[i][2] = dp[i - 1][0] + 1;
        }
        else{
            dp[i][3] = dp[i - 1][0] + 1;
        }

        dp[i][2] = std::min({dp[i][2], dp[i - 1][3] + 1, dp[i - 1][1] + 1});
        dp[i][3] = std::min(dp[i][3], dp[i - 1][2] + 1);
    }

    std::cout << std::min({dp[n][0], dp[n][1], dp[n][2], dp[n][3]});
    
    return 0;
}