#include<bits/stdc++.h> #define int long long using namespace std; namespace Fast{ inline long long fr(){ register long long x=0,f=1; static char c=getchar(); while(c<'0'||c>'9'){ if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9'){ x=x<<1+x<<3+c^48; c=getchar(); } return x*f; } inline void fw(long long x){ if(x==0){ putchar('0'); return; } if(x<0){ x=-x; putchar('-'); } stack<char> s; while(x){ s.push((x%10)+'0'); x/=10; } while(!s.empty()){ putchar(s.top()); s.pop(); } } inline void CCF(int opt){ ios::sync_with_stdio(false); if(opt==0){ cout.tie(0); return; } if(opt>=1) cin.tie(0); if(opt>=2) cout.tie(0); } inline void DEBUG(){ puts("IAKIOI"); } } using namespace Fast; int a[15],cnt,n; bool f[15][15],c[15]; bool check(int x){ int cnt=0; memset(c,false,sizeof(c)); for(int i=1;i<=n;i++){ if(c[i]) continue; cnt++; vector<int> vec; vec.clear(); vec.push_back(i); c[i]=true; for(int j=1;j<=n;j++){ if(c[j]) continue; if(!f[i][j]){ bool fl=true; for(int k=0;k<vec.size();k++){ if(f[vec[k]][j]){ fl=false; break; } } if(fl){ vec.push_back(j); c[j]=true; } } } } return cnt<=x; } signed main(){ n=fr(); for(int i=1;i<=n;i++) a[i]=fr(); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(__gcd(a[i],a[j])!=1) f[i][j]=true; } } int l=0,r=n; while(l<=r){ int mid=(l+r)/2; if(check(mid)) r=mid-1; else l=mid+1; } fw(l); return 0; }