#include <bits/stdc++.h>

#define IL __inline__ __attribute__((always_inline))

#define For(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++ i)
#define FOR(i, a, b) for (int i = (a), i##end = (b); i < i##end; ++ i)
#define Rep(i, a, b) for (int i = (a), i##end = (b); i >= i##end; -- i)
#define REP(i, a, b) for (int i = (a) - 1, i##end = (b); i >= i##end; -- i)

typedef long long LL;

template <class T>
IL bool chkmax(T &a, const T &b) {
  return a < b ? ((a = b), 1) : 0;
}

template <class T>
IL bool chkmin(T &a, const T &b) {
  return a > b ? ((a = b), 1) : 0;
}

template <class T>
IL T mymax(const T &a, const T &b) {
  return a > b ? a : b;
}

template <class T>
IL T mymin(const T &a, const T &b) {
  return a < b ? a : b;
}

template <class T>
IL T myabs(const T &a) {
  return a > 0 ? a : -a;
}

const int INF = 0X3F3F3F3F;
const double EPS = 1E-8, PI = acos(-1.0);

#define DEBUG(...) fprintf(stderr, __VA_ARGS__)
#define OK DEBUG("Passing [%s] in LINE %d...\n", __FUNCTION__, __LINE__)
#define SZ(x) ((int)(x).size())

const int MAXN = 2000 + 5, MAXM = 10000000 + 5, MAXK = 1000000 + 5;

int pri[MAXM], val[MAXM], p_cnt;
bool np[MAXM];

IL void init(int n) {
  np[1] = 1;
  For(i, 2, n) {
    if (!np[i]) {
      pri[++ p_cnt] = i;
    }
    for (int j = 1; j <= p_cnt && pri[j] * i <= n; ++ j) {
      np[i * pri[j]] = 1;
      if (i % pri[j] == 0) {
        break;
      }
    }
  }
  For(i, 1, n) {
    val[i] = i % 2 ? 1 + np[i] * 2 : 2;
  }
}

int pos[MAXN];
bool ok[MAXM];
std::vector<int> dpos[2];

namespace NetworkFlow {
int s, t;

struct Edge {
  int from, to, resi;

  Edge() {}
  Edge(int _f, int _t, int _c) : from(_f), to(_t), resi(_c) {}
} edges[MAXM * 2];

std::vector<int> adj[MAXN];
int cnt;

IL void addEdge(int u, int v, int c) {
  edges[cnt] = Edge(u, v, c), adj[u].push_back(cnt);
  ++ cnt;
  edges[cnt] = Edge(v, u, 0), adj[v].push_back(cnt);
  ++ cnt;
}

int dist[MAXN], cur[MAXN];

IL bool BFS() {
  static int que[MAXN], vis[MAXN], num;
  ++ num;
  int l = 1, r = 0;
  que[++ r] = s, dist[s] = 0, vis[s] = num;
  while (l <= r) {
    int u = que[l ++];
    FOR(k, 0, SZ(adj[u])) {
      Edge &e = edges[adj[u][k]];
      if (vis[e.to] != num && e.resi)
        que[++ r] = e.to, dist[e.to] = dist[u] + 1, vis[e.to] = num;
    }
  }
  return vis[t] == num;
}

int DFS(int u, int x) {
  if (!x || u == t) {
    return x;
  }
  int flow = 0, f;
  for (int &k = cur[u]; k < SZ(adj[u]); ++ k) {
    Edge &e = edges[adj[u][k]];
    if (dist[e.to] == dist[u] + 1 && (f = DFS(e.to, mymin(x, e.resi)))) {
      edges[adj[u][k]].resi -= f, edges[adj[u][k] ^ 1].resi += f;
      flow += f, x -= f;
      if (!x)
        break;
      }
  }
  return flow;
}

IL int dinic() {
  int flow = 0;
  while (BFS()) {
    memset(cur, 0, sizeof cur);
    flow += DFS(s, INF);
  }
  return flow;
}

IL int solve() {
  int x = SZ(dpos[0]), y = SZ(dpos[1]);
  s = x + y + 1, t = x + y + 2;
  FOR(i, 0, x) {
    FOR(j, 0, y) {
      if (!np[myabs(dpos[0][i] - dpos[1][j])]) {
        addEdge(i + 1, j + 1 + x, 1);
      }
    }
  }
  For(i, 1, x) {
    addEdge(s, i, 1);
  }
  For(i, 1, y) {
    addEdge(i + x, t, 1);
  }
  return dinic();
}
}

int main() {
  init(10000000);
  int n;
  scanf("%d", &n);
  For(i, 1, n) {
    scanf("%d", &pos[i]);
    ok[pos[i]] = 1;
  }
  For(i, 1, 10000001) {
    if (ok[i] ^ ok[i - 1]) {
      dpos[i % 2].push_back(i);
    }
  }
  int k = NetworkFlow::solve(), x = (SZ(dpos[0]) - k) / 2, y = (SZ(dpos[1]) - k) / 2;
  printf("%d\n", k + (x + y) * 2 + (SZ(dpos[0]) - k) % 2 * 3);
  return 0;
}


Measured memory_bytes: 63872