#include<bits/stdc++.h> #define int long long using namespace std; namespace Fast{ inline long long fr(){ register long long x = 0,f = 1; static char c = getchar(); while (c < '0' || c > '9'){ if (c == '-'){ f = -1; } c = getchar(); } while (c >= '0' && c <= '9'){ x = (x << 1) + (x << 3) + (c ^ 48); c = getchar(); } return x * f; } inline void fw(long long x){ if (x == 0){ putchar('0'); return ; } if (x < 0){ x = -x; putchar('-'); } stack <char> s; while (x){ s.push((x % 10) + '0'); x /= 10; } while (!s.empty()){ putchar(s.top()); s.pop(); } } inline void CCF(int opt){ ios::sync_with_stdio(false); if (opt == 0){ cout.tie(0); return ; } if (opt >= 1){ cin.tie(0); } if (opt >= 2){ cout.tie(0); } } inline void DEBUG(){ puts("IAKIOI"); } } using namespace Fast; int a[15],cnt,n; bool f[15][15],c[15]; bool check(int x){ int cnt = 0; memset(c,false,sizeof(c)); for (int i = 1;i <= n;i++){ if (c[i]){ continue; } cnt++; vector <int> vec; vec.clear(); vec.push_back(i); c[i] = true; for (int j = 1;j <= n;j++){ if (c[j]){ continue; } if (!f[i][j]){ 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); } signed main(){ n = fr(); for (int i = 1;i <= n;i++){ a[i] = fr(); } 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 = 0,r = n; while (l <= r){ int mid = (l + r) / 2; if (check(mid)){ r = mid - 1; } else{ l = mid + 1; } } fw(l); return 0; }