#include "bits/stdc++.h"
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;


// Source: bqi343+Me
// Tested On:
// Fast prime sieve in O(NloglogN)
// Also finds the number of primes <= x
template <int N = 100007>
struct Sieve {
  bitset<N> isPrime;
  vector<int> primes, cum;
  Sieve() {
    isPrime.set();
    isPrime[0] = isPrime[1] = 0;
    for (int i = 4; i < N; i += 2) isPrime[i] = 0;
    for (int i = 3; i * i < N; i += 2)
      if (isPrime[i])
        for (int j = i * i; j < N; j += 2 * i) isPrime[j] = 0;
    for (int i = 0; i < N; i++) {
      if (isPrime[i]) primes.push_back(i);
      cum.push_back(primes.size());
    }
  }
};

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  Sieve<200007> S;
  enum {
    SAME, // this is separate from 1
    ONE,
    EVEN, // this is separate from 1
    ODD, // this is separate from 1
  };

  array<int, 4> dp = {0};
  int n;
  cin >> n;
  vi a(n);
  for (auto& x :a) cin >> x;
  const int INF = 1e9;
  dp[EVEN] = 1, dp[ODD] = 1;
  if (a[0] != 1) dp[ONE] = 1;
  else dp[ONE] = 0, dp[SAME] = INF;
  rep(i, 1, n) {
    array<int, 4> ndp = {INF, INF, INF, INF};
    if (S.isPrime[a[i] + a[i-1]]) {
      // Keep things the same.
      ndp[SAME] = min(ndp[SAME], dp[SAME]);
    }
    if (S.isPrime[a[i] + 1]) {
      ndp[SAME] = min(ndp[SAME], dp[ONE]);
    }
    if (a[i] == 1) {
      // We can keep it the same if the previous number is
      // one or an undecided even number.
      ndp[ONE] = min(ndp[ONE], dp[ONE]);
      ndp[ONE] = min(ndp[ONE], dp[EVEN]);

      // We can change it to some random odd number if
      // the previous number is even.
      ndp[ODD] = min(ndp[ODD], dp[EVEN] + 1);
      if (a[i-1]%2 == 0) {
        ndp[ODD] = min(ndp[ODD], dp[SAME] + 1);
      }

      // We can change it to some random even number if
      // the previous number is odd.
      ndp[EVEN] = min(ndp[EVEN], dp[ODD] + 1);
      ndp[EVEN] = min(ndp[EVEN], dp[ONE] + 1);
      if (a[i-1]%2 == 1) {
        ndp[EVEN] = min(ndp[EVEN], dp[SAME] + 1);
      }
    } else if (a[i]%2 == 1) {
      // We can keep it the same if the previous number is undecided
      // even.
      ndp[SAME] = min(ndp[SAME], dp[EVEN]);

      // We can change it to some random odd number if
      // the previous number is even.
      ndp[ODD] = min(ndp[ODD], dp[EVEN] + 1);
      if (a[i-1]%2 == 0) {
        ndp[ODD] = min(ndp[ODD], dp[SAME] + 1);
      }

      // We can change it to some random even number if
      // the previous number is odd.
      ndp[EVEN] = min(ndp[EVEN], dp[ODD] + 1);
      ndp[EVEN] = min(ndp[EVEN], dp[ONE] + 1);
      if (a[i-1]%2 == 1) {
        ndp[EVEN] = min(ndp[EVEN], dp[SAME] + 1);
      }

      // We can change it to one if the previous number is one.
      ndp[ONE] = min(ndp[ONE], dp[ONE] + 1);
      ndp[ONE] = min(ndp[ONE], dp[EVEN] + 1);
      if (S.isPrime[a[i-1]+1]) {
        ndp[ONE] = min(ndp[ONE], dp[SAME] + 1);
      }
    } else if (a[i]%2 == 0) {
      // We can keep it the same if the previous number is undecided
      // even.
      ndp[SAME] = min(ndp[SAME], dp[ODD]);

      // We can change it to some random odd number if
      // the previous number is even.
      ndp[ODD] = min(ndp[ODD], dp[EVEN] + 1);
      if (a[i-1]%2 == 0) {
        ndp[ODD] = min(ndp[ODD], dp[SAME] + 1);
      }

      // We can change it to some random even number if
      // the previos number is odd.
      ndp[EVEN] = min(ndp[EVEN], dp[ODD] + 1);
      ndp[EVEN] = min(ndp[EVEN], dp[ONE] + 1);
      if (a[i-1] != 1 && a[i-1]%2 == 1) {
        ndp[EVEN] = min(ndp[EVEN], dp[SAME] + 1);
      }

      // We can change it to one if the previous number is one.
      ndp[ONE] = min(ndp[ONE], dp[ONE] + 1);
      ndp[ONE] = min(ndp[ONE], dp[EVEN] + 1);
      if (S.isPrime[a[i-1]+1]) {
        ndp[ONE] = min(ndp[ONE], dp[SAME] + 1);
      }
    }
    dp = std::move(ndp);
  }
  cout << *min_element(all(dp)) << '\n';
}