#include<bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
typedef double db;

const int N=20005,K=15;
int n,a[N];
int dp[N][4];
int isp[N];
vector<int> ve;

void seive(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!isp[i]) ve.pb(i);
        for(int p:ve)
        {
            if(1ll*p*i>n) break;
            isp[p*i]=1;
            if(i%p==0) break;
        }
    }
}

void input()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
}

void upd(int&x,int y) {if(x>y) x=y;}

void solve()
{
    input();
    memset(dp,0x3f,sizeof(dp));
    dp[1][0]=0,dp[1][1]=dp[1][2]=dp[1][3]=1;
    for(int i=2;i<=n;i++)
    {
        if(!isp[a[i]+a[i-1]]) upd(dp[i][0],dp[i-1][0]);
        if(a[i]%2==0) upd(dp[i][0],dp[i-1][1]);
        else upd(dp[i][0],dp[i-1][2]);
        if(!isp[a[i]+1]) upd(dp[i][0],dp[i-1][3]);

        if(a[i-1]%2==0) upd(dp[i][1],dp[i-1][0]+1);
        upd(dp[i][1],dp[i-1][2]+1);

        if(a[i-1]%2) upd(dp[i][2],dp[i-1][0]+1);
        upd(dp[i][2],dp[i-1][1]+1);
        upd(dp[i][2],dp[i-1][3]+1);

        if(!isp[a[i-1]+1]) upd(dp[i][3],dp[i-1][0]+1);
        upd(dp[i][3],dp[i-1][2]+1);
        upd(dp[i][3],dp[i-1][3]+1);
        //cerr<<' '<<i<<' '<<dp[i][0]<<' '<<dp[i][1]<<' '<<dp[i][2]<<' '<<dp[i][3]<<endl;
    }
    int ans=n;
    for(int i=0;i<4;i++) upd(ans,dp[n][i]);
    printf("%d\n",ans);
}

int main()
{
    seive(N-5);
    solve();
}