#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,a[N],b[N*2],f[N],f0[N],f1[N],g[N];
bool chk(int x){
	for(int i=2;i*i<=x;i++) if(x%i==0) return 0;
	return 1;
}
int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin>>n;
	for(int i=2;i<N*2;i++) b[i]=chk(i);
	for(int i=1;i<=n;i++) cin>>a[i];
	f0[1]=f1[1]=1;g[1]=a[1]!=1;
	for(int i=2;i<=n;i++){
		f[i]=a[i]%2?f0[i-1]:f1[i-1];
		if(b[a[i]+1]) f[i]=min(f[i],g[i-1]);
		if(b[a[i]+a[i-1]]) f[i]=min(f[i],f[i-1]);
		f0[i]=min(f1[i-1],g[i-1]);
		if(a[i-1]%2) f0[i]=min(f0[i],f[i-1]);
		f1[i]=f0[i-1];
		if(a[i-1]%2==0) f1[i]=min(f1[i],f[i-1]);
		g[i]=min({g[i-1],f0[i-1],(!b[a[i]+1])*N+f[i-1]})+(a[i]!=1);
		f0[i]++;f1[i]++;
	}
	cout<<min({f[n],f0[n],f1[n],g[n]});
	return 0;
}