#include <bits/stdc++.h>

const int N = 1e5 + 5;
const int INF = 0x3f3f3f3f;
int n, a[N], f[N][4];

int main()
{
  std::cin >> n;
  for (int i = 1; i <= n; i++)
    std::cin >> a[i];
  for (int i = 1; i <= n; i++)
    f[i][0] = f[i][1] = f[i][2] = f[i][3] = INF;

  f[1][0] = 0;
  f[1][1] = !(a[1] == 1);
  f[1][2] = !(a[1] % 2);
  f[1][3] = (a[1] % 2 == 1 && a[1] > 1) ? 0 : 1;

  auto is_prime = [&](const int &x)
  {
    for (int i = 2; i * i <= x; i++)
      if (x % i == 0)
        return false;

    return true;
  };

  for (int i = 1; i <= n; i++)
  {
    if (is_prime(a[i] + a[i + 1]))
      f[i + 1][0] = std::min(f[i + 1][0], f[i][0]);
    if (a[i] % 2 == 1)
      f[i + 1][2] = std::min(f[i + 1][2], f[i][0] + 1);
    if (a[i] % 2 == 0)
      f[i + 1][3] = std::min(f[i + 1][3], f[i][0] + 1);
    if (is_prime(a[i] + 1))
      f[i + 1][1] = std::min(f[i + 1][1], f[i][0] + 1);
    if (is_prime(a[i + 1] + 1))
      f[i + 1][0] = std::min(f[i + 1][0], f[i][1]);
    f[i + 1][2] = std::min(f[i + 1][2], f[i][1] + 1);
    f[i + 1][1] = std::min(f[i + 1][1], f[i][1] + 1);
    if (a[i + 1] % 2 == 1)
      f[i + 1][0] = std::min(f[i + 1][0], f[i][2]);
    f[i + 1][1] = std::min(f[i + 1][1], f[i][2] + 1);
    f[i + 1][3] = std::min(f[i + 1][3], f[i][2] + 1);
    if (a[i + 1] % 2 == 0)
      f[i + 1][0] = std::min(f[i + 1][0], f[i][3]);
    f[i + 1][2] = std::min(f[i + 1][2], f[i][3] + 1);
  }
  int ans = f[n][0];
  for (int i = 1; i <= 3; i++)
    ans = std::min(ans, f[n][i]);
  std::cout << ans << '\n';
  return 0;
}