#include <bits/stdc++.h> using namespace std; int a[20],cnt[20],gr[20][20],minx=2147483647,n; int f[20][20]; int gcd(int a,int b) { if(b==0) return a; else return gcd(b,a%b); } 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; return 0; }