#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; }