#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
using namespace std;
 
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
 
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; }



const int MAX_L = 2100;
const int MAX_R = 2100;

struct Graph {
	int L;
	vector<int> list[MAX_L];

	void init(int n = 0) { L = n; for (int i = 0; i < MAX_L; ++i) list[i].clear(); }
	inline vector<int>& operator [] (int i) { return list[i]; }
	void addedge(int from, int to) { list[from].push_back(to); }
	friend ostream& operator << (ostream& s, const Graph& G) {
		s << endl; for (int i = 0; i < G.L; ++i) { s << i << " : " << G.list[i] << endl; }return s;
	}
};

Graph G;

int L = 0;
bool seen[MAX_L];
bool matched[MAX_L];
int level[MAX_L];
int matching[MAX_R];

void hobfs(Graph &G) {
	queue<int> que;
	for (int left = 0; left < L; ++left) {
		level[left] = -1;
		if (!matched[left]) {
			que.push(left);
			level[left] = 0;
		}
	}
	level[L] = L;
	while (!que.empty()) {
		int left = que.front();
		que.pop();
		for (int i = 0; i < G[left].size(); ++i) {
			int right = G[left][i];
			int next = matching[right];
			if (level[next] == -1) {
				level[next] = level[left] + 1;
				que.push(next);
			}
		}
	}
}

bool hodfs(Graph &G, int left) {
	if (left == L) return true;
	if (seen[left]) return false;
	seen[left] = true;
	for (int i = 0; i < G[left].size(); ++i) {
		int right = G[left][i];
		int next = matching[right];
		if (level[next] > level[left] && hodfs(G, next)) {
			matching[right] = left;
			return true;
		}
	}
	return false;
}

int Hopcroft_Karp(Graph &G) {
	L = G.L;
	for (int i = 0; i < MAX_R; ++i) matching[i] = L;
	memset(matched, 0, sizeof(matched));

	int res = 0;
	while (true) {
		hobfs(G);
		memset(seen, 0, sizeof(seen));
		bool finished = true;
		for (int left = 0; left < L; ++left) {
			if (!matched[left] && hodfs(G, left)) {
				matched[left] = true;
				++res;
				finished = false;
			}
		}
		if (finished) break;
	}
	return res;
}


const int MAX = 10001000;
bool IsPrime[MAX];
vector<int> Era(int n = MAX) {
    vector<int> res;
	IsPrime[0] = false; IsPrime[1] = false; 
	for (int i = 2; i < n; ++i) IsPrime[i] = true;
	for (int i = 2; i < n; ++i) {
		if (IsPrime[i]) {
            res.push_back(i);
			for (int j = i*2; j < n; j += i) IsPrime[j] = false;
		}
	}
    return res;
}


int N;
int a[MAX];
int diff[MAX];

int solve() {
  diff[0] = a[0];
  for (int i = 0; i+1 < MAX; ++i) {
	diff[i+1] = a[i+1] ^ a[i];
  }
  vector<int> odd, even;
  for (int i = 0; i < MAX; ++i) {
	if (diff[i] == 1) {
	  if (i % 2 == 0) even.push_back(i);
	  else odd.push_back(i);
	}
  }

  G.init(odd.size());
  
  for (int i = 0; i < odd.size(); ++i) {
	for (int j = 0; j < even.size(); ++j) {
	  if (IsPrime[abs(odd[i] - even[j])]) {
		G.addedge(i, j);
	  }
	}
  }

  int Max = Hopcroft_Karp(G);
  int evenrem = even.size() - Max;
  int oddrem = odd.size() - Max;

  int res = Max + evenrem / 2 * 2 + oddrem / 2 * 2;
  if (evenrem & 1) {
	res += 3;
  }
				 
  return res;
}

int main() {
  Era();
  while (cin >> N) {
	memset(a, 0, sizeof(a));
	for (int i = 0; i < N; ++i) {
	  int x;
	  cin >> x;
	  a[x] = 1;
	}
	cout << solve() << endl;
  }
}




















Measured memory_bytes: 88400