#include <bits/stdc++.h>
using namespace std;
int st[4000000];
int a[1000000];
int n;
void build(int x, int xl, int xr){
if(xl==xr) st[x]=a[xl];
else{
int m=(xl+xr)/2;
build(x*2+1,xl,m);
build(x*2+2,m+1,xr);
st[x]=__gcd(st[x*2+1],st[x*2+2]);
}
return;
}
int f(int x, int xl, int xr, int l, int r){
if(xl>=l && xr<=r) return st[x];
if(xr<l || xl>r) return 0;
int m=(xl+xr)/2;
return __gcd(f(x*2+1,xl,m,l,r),f(x*2+2,m+1,xr,l,r));
}
int check(vector<int> p){
int g=0,l=0,sk=p.size();
for(int i=0; i<sk; i++) a[p[i]]++;
for(int i=0; i<sk; i++) g=__gcd(g,a[p[i]]);
for(int i=0; i<sk; i++) a[p[i]]--;
for(int i=sk-1; i>=0; i--){
if(p[i]>l) g=__gcd(g,f(0,0,n-1,l,p[i]-1));
l=p[i]+1;
}
if(l<n) g=__gcd(g,f(0,0,n-1,l,n-1));
return (g==1?1:0);
}
int main()
{
cin>>n;
for(int i=0; i<n; i++) cin>>a[i];
build(0,0,n-1);
if(st[0]==1){
cout<<"0";
return 0;
}
int sk=1;
while(sk<6){
vector<int> p(sk,0);
while(p[sk-1]!=n){
int r=check(p);
if(r){
cout<<sk;
return 0;
}
int ne=-1;
p[0]++;
for(int i=0; i<sk-1; i++){
if(p[i]==n){
p[i+1]++;
ne=i+1;
}
}
if(ne!=-1){
for(int i=0; i<ne; i++) p[i]=p[ne];
}
}
sk++;
}
return 0;
}
