#include<bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f3f3f3f 
#define GG ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define cnot cout<<"NO"<<"\n"
#define cyes cout<<"YES"<<"\n"
#define pb push_back
#define x0 first
#define y0 second
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef pair<int,string>Pis;
typedef pair<int,int>Pii;
const int N=2e5+10,mod=1e9+7,M=1e6+10;
int dp[N][20];
int a[N];
int check(int x){
    if(x==2)return 1;
    for(int i=2;i*i<=x;i++){
        if(x%i==0){
            return 0;
        }
    }
    return 1;
}
void solve(){
   int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
      for(int i=0;i<=n;i++){
        for(int j=0;j<=18;j++){
        dp[i][j]=inf;
        }
    }
   dp[1][0]=0;
    dp[1][1]=1;
    dp[1][2]=1;
    dp[1][3]=1;
    for(int i=2;i<=n;i++){ 
        if(check(a[i]+a[i-1])){
            dp[i][0]=min(dp[i-1][0],dp[i][0]);
        }
        if(check(a[i]+1)){
            dp[i][0]=min(dp[i][0],dp[i-1][1]+1);
        }
        if(a[i]%2==0){
          dp[i][0]=min({dp[i-1][3],dp[i][0]});
        }
        else {
           dp[i][0]=min({dp[i-1][2],dp[i][0]});
        }
        if(a[i-1]%2==1){
            dp[i][2]=min(dp[i-1][0]+1,dp[i][2]);
        }
        else {
            if(check(a[i-1]+1)){
                dp[i][1]=min(dp[i-1][0]+1,dp[i][1]);
            }
            dp[i][3]=min(dp[i-1][0]+1,dp[i][3]);
        }
        if(a[i]==1){
            dp[i][0]=min(dp[i][0],dp[i-1][1]);
            dp[i][1]=min(dp[i][1],dp[i][0]);
            dp[i][0]=min(dp[i][1],dp[i][0]);
        }
        dp[i][2]=min({dp[i][2],dp[i-1][1]+1,dp[i-1][3]+1});
        dp[i][1]=min({dp[i-1][2]+1,dp[i][1],dp[i-1][1]+1});
        dp[i][3]=min(dp[i-1][2]+1,dp[i][3]);
    }
    int ans=inf;
        ans=min({ans,dp[n][0],dp[n][1],dp[n][2],dp[n][3]});
        cout<<ans;
    

}
signed main(){
    GG;

    int _t=1;
    //cin>>_t;
    while(_t--){
        solve();
    }
    
}