#include <bits/stdc++.h> using namespace std; int a[20],cnt[20],gr[20][20],minx=2147483647,n,f[20][20]; void dfs(int now,int g) { bool flag=1; if(now>n) { minx=min(minx,g); return ; } for(int i=1;i<=g;i++) { flag=1; for(int j=1;j<=cnt[i];j++) { if(f[now][gr[i][j]]==0) { flag=0; break; } } if(flag) { gr[i][++cnt[i]]=now; dfs(now+1,g); --cnt[i]; } } gr[g+1][++cnt[g+1]]=now; dfs(now+1,g+1); return ; } int main() { cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; for(int j=1;j<i;j++) { if(__gcd(a[i],a[j])==1) f[i][j]=f[j][i]=1; } } dfs(1,0); cout<<minx<<endl; return 0; }