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