#include<bits/stdc++.h> using namespace std; bool f[15][15],c[15]; int a[15],n; bool check(int x){ memset(c,false,sizeof(c)); int cnt=0; for(int i=1;i<=n;i++){ if(c[i])continue; cnt++; c[i]=true; vector<int> vec; vec.clear(); vec.push_back(i); for(int j=i+1;j<=n;j++){ if(c[j])continue; 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; } int main(){ cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; 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=1,r=n; while(l<=r){ int mid=(l+r)/2; if(check(mid))r=mid-1; else l=mid+1; } cout<<l; return 0; }