#include <bits/stdc++.h>

#ifdef LOCAL_DEBUG
#include "debug.h"
#else
#define dbg(...) (void)0
#endif
using u32 = unsigned int;
using i64 = long long;

namespace skadi {

    struct Sieve {
        std::vector<int> primes;
        std::vector<int> factor;
        std::vector<bool> is_prime;

        Sieve(int n) : factor(n + 1, -1), is_prime(n + 1, true) {
            is_prime[0] = is_prime[1] = false;
            for (int i = 2; i <= n; i++) {
                if (is_prime[i]) {
                    primes.push_back(i);
                    factor[i] = i;
                }
                for (int j = 0; j < (int) primes.size() && i * primes[j] <= n; j++) {
                    is_prime[i * primes[j]] = false;
                    factor[i * primes[j]] = primes[j];
                    if (i % primes[j] == 0) break;
                }
            }
        }
    } seive(1e6);

    int f[100005][2][2][2];

    void solve() {
        auto &is_prime = seive.is_prime;
        int n;
        std::cin >> n;
        std::vector<int> a(n + 1);
        for (int i = 1; i <= n; i++) std::cin >> a[i];
        if (n <= 2) {
            if (is_prime[a[1] + a[2]]) std::cout << "0\n";
            else std::cout << "1\n";
            return;
        }
        if (is_prime[a[1] + a[2]] && is_prime[a[2] + a[3]]) f[3][0][0][0] = 0;
        else f[3][0][0][0] = 114514;
        if (is_prime[a[2] + a[3]]) f[3][0][0][1] = 1;
        else f[3][0][0][1] = 114514;
        if ((a[3] % 2 == a[1] % 2) || ((a[1] == 1 || a[3] == 1) && is_prime[a[1] + a[3]])) f[3][0][1][0] = 1;
        else f[3][0][1][0] = 114514;
        f[3][0][1][1] = 2;
        if (is_prime[a[1] + a[2]]) f[3][1][0][0] = 1;
        else f[3][1][0][0] = 114514;
        f[3][1][0][1] = 2;
        f[3][1][1][0] = 2;
        f[3][1][1][1] = 3;
        for (int i = 4; i <= n; i++) {
            // 000
            if (is_prime[a[i] + a[i - 1]] && is_prime[a[i - 1] + a[i - 2]])
                f[i][0][0][0] = std::min(f[i - 1][0][0][0], f[i - 1][0][0][1]);
            else f[i][0][0][0] = 114514;
            // 001
            if (is_prime[a[i] + a[i - 1]]) f[i][0][0][1] = std::min(f[i - 1][0][1][0], f[i - 1][0][1][1]);
            else f[i][0][0][1] = 114514;
            // 010
            if ((a[i] % 2 == a[i - 2] % 2) || ((a[i - 2] == 1 || a[i] == 1) && is_prime[a[i - 2] + a[i]]))
                f[i][0][1][0] = std::min(f[i - 1][1][0][0], f[i - 1][1][0][1]);
            else f[i][0][1][0] = 114514;
            //011
            if ((a[i] % 2 != a[i - 3] % 2) || (is_prime[a[i] + 1] && is_prime[a[i - 3] + 1]))
                f[i][0][1][1] = f[i - 1][1][1][0];
            else f[i][0][1][1] = 114514;
            f[i][0][1][1] = std::min(f[i][0][1][1], f[i - 1][1][1][1]);
            //100
            f[i][1][0][0] = std::min(f[i - 1][0][0][0], f[i - 1][0][0][1]) + 1;
            //101
            f[i][1][0][1] = std::min(f[i - 1][0][1][0], f[i - 1][0][1][1]) + 1;
            //110
            f[i][1][1][0] = std::min(f[i - 1][1][0][0], f[i - 1][1][0][1]) + 1;
            //111;
            f[i][1][1][1] = std::min(f[i - 1][1][1][0], f[i - 1][1][1][1]) + 1;
        }
        std::cout << std::min({f[n][0][0][0], f[n][0][1][0], f[n][0][0][1], f[n][0][1][1], f[n][1][0][0], f[n][1][0][1],
                               f[n][1][1][0], f[n][1][1][1]}) << '\n';
    }

} // namespace skadi

int main() {
#ifndef LOCAL_DEBUG
    std::cin.tie(nullptr)->sync_with_stdio(false);
#endif
    int t = 1;
    // std::cin >> t;
    while (t--) {
        skadi::solve();
    }
    return 0;
}