#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10,inf=1e18;
int n,cnt,a[N],isp[N],f[N][5],pr[N];//set<pair<int,int> >s;
inline int read(){
    int r=0,f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c))r=(r<<1)+(r<<3)+(c^48),c=getchar();
    return r*f;
}
void put(int x){
    if(x<0){putchar('-');x=~x+1;}
    if(x>9)put(x/10);
    putchar(x%10+'0');
}
signed main(){
  //  freopen("cpp.in","r",stdin);
  //  freopen("cpp.out","w",stdout);
    n=read(),isp[1]=1;
    for(int i=1;i<=n;i++)a[i]=read();
    for(int i=2;i<=2e5;i++){
        if(!isp[i])pr[++cnt]=i;
        for(int j=1;j<=cnt&&pr[j]*i<=2e5;j++){
            isp[pr[j]*i]=1;
            if(i%pr[j]==0)break;
        }
    }
    for(int i=1;i<=n;i++){
        f[i][1]=min(f[i-1][2],f[i-1][3])+1;
        f[i][2]=min(f[i-1][2],f[i-1][1])+1;
        if(!isp[a[i-1]+1])f[i][2]=min(f[i][2],f[i-1][4]+1);
        f[i][3]=f[i-1][1]+1;
        if(a[i-1]&1)f[i][1]=min(f[i][1],f[i-1][4]+1);
        else f[i][3]=min(f[i][3],f[i-1][4]+1);
        if(a[i]&1)f[i][4]=f[i-1][1];
        else{
            f[i][4]=f[i-1][3];
            if(!isp[a[i]+1])f[i][4]=min(f[i][4],f[i-1][2]);
        }
        if(!isp[a[i]+a[i-1]])f[i][4]=min(f[i][4],f[i-1][4]);
    }
//    for(int i=1;i<=n;i++,putchar('\n'))for(int j=1;j<=4;j++)cout<<f[i][j]<<" ";
    int ans=inf;
    for(int i=1;i<=4;i++)ans=min(ans,f[n][i]);
    return put(ans),puts(""),0;
}