#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
using f64 = double_t;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  constexpr int maxn = 200000;
  vector<bool> ip(maxn + 1, true);
  for (int i = 2; i <= maxn; i += 1) {
    if (ip[i]) {
      for (int j = i + i; j <= maxn; j += i) { ip[j] = false; }
    }
  }
  int n;
  cin >> n;
  vector<int> a(n);
  for (int &ai : a) { cin >> ai; }
  // org, 1, odd > 1, even
  vector<int> f = {0, 1, 1, 1};
  if (a[0] == 1) { f[1] = 0; }
  for (int i = 1; i < n; i += 1) {
    vector<int> g = {n + 1, n + 1, n + 1, n + 1};
    for (int j = 0; j < 4; j += 1) {
      int w = 1;
      if (j == 0) {
        w = 0;
      } else if (j == 1) {
        w = a[i] != 1;
      }
      for (int k = 0; k < 4; k += 1) {
        if (k == 0) {
          if (j == 0 and not ip[a[i] + a[i - 1]]) { continue; }
          if (j == 1 and not ip[a[i - 1] + 1]) { continue; }
          if (j == 2 and a[i - 1] % 2) { continue; }
          if (j == 3 and a[i - 1] % 2 == 0) { continue; }
        }
        if (k == 1) {
          if (j == 0 and not ip[a[i] + 1]) { continue; }
          if (j == 2) { continue; }
        }
        if (k == 2) {
          if (j == 0 and a[i] % 2) { continue; }
          if (j == 1) { continue; }
          if (j == 2) { continue; }
        }
        if (k == 3) {
          if (j == 0 and a[i] % 2 == 0) { continue; }
          if (j == 3) { continue; }
        }
        g[j] = min(g[j], f[k] + w);
      }
    }
    f.swap(g);
  }
  cout << ranges::min(f);
}