#include <bits/stdc++.h>
using namespace std;
template <class T>
string ToString(T t) {
  stringstream s;
  s << t;
  return s.str();
}
template <class T>
void ToOther(T& t, string a) {
  stringstream s(a);
  s >> t;
}
int n;
map<long long, int> v[10];
long long a[10];
int d[1 << 10];
int calc(int x) {
  map<long long, int>::iterator it;
  int r = 0;
  for (it = v[x].begin(); it != v[x].end(); it++) {
    r += it->second;
  }
  return r;
}
int Get(int st) {
  int r = -1;
  for (int i = 0; i <= n; i++)
    if (st >> i & 1) {
      if (r == -1)
        r = i;
      else if (a[i] > a[r])
        r = i;
    }
  return r;
}
int calc(int x, int y) {
  map<long long, int> t = v[x];
  map<long long, int>::iterator it;
  for (it = v[y].begin(); it != v[y].end(); it++) {
    t[it->first] -= it->second;
  }
  int r = 0;
  for (it = t.begin(); it != t.end(); it++) {
    r += it->second;
  }
  return r;
}
int cost(int x, int y) {
  if (x == n && y == n) return 0;
  if (x == n || y == n) return 0;
  long long A = a[x];
  long long B = a[y];
  if (A % B == 0) {
    return -calc(y);
  } else if (B % A == 0) {
    return -calc(x);
  }
  return -(1 << 30);
}
bool can(int idx, int st1, int st2) {
  if (st1 >> idx & 1) st1 ^= (1 << idx);
  if (st2 >> idx & 1) st2 ^= (1 << idx);
  if (idx == n) return 1;
  vector<long long> t;
  for (int i = 0; i < n; i++)
    if (st1 >> i & 1) {
      t.push_back(a[i]);
    }
  sort((t).begin(), (t).end(), greater<long long>());
  long long now = 1;
  for (int i = 0; i < t.size(); i++) {
    for (int j = 0; j < i; j++)
      if (t[j] % t[i] == 0) goto E;
    if (now > a[idx] / t[i]) return 0;
    now *= t[i];
  E:;
  }
  t.clear();
  for (int i = 0; i < n; i++)
    if (st2 >> i & 1) {
      t.push_back(a[i]);
    }
  sort((t).begin(), (t).end(), greater<long long>());
  for (int i = 0; i < t.size(); i++) {
    for (int j = 0; j < i; j++)
      if (t[j] % t[i] == 0) goto E2;
    if (now > a[idx] / t[i]) return 0;
    now *= t[i];
  E2:;
  }
  if (a[idx] % now == 0) return 1;
  return 0;
}
int main() {
  cin >> n;
  a[n] = (1ll << 60);
  for (int i = 0; i < n; i++) {
    long long t;
    cin >> t;
    a[i] = t;
    int L = (int)sqrt(double(t));
    for (int k = 2; k <= L; k++)
      if (t % k == 0) {
        long long c = 0;
        while (t % k == 0) c++, t /= k;
        v[i][k] = c;
      }
    if (t != 1) v[i][t] = 1;
  }
  int all = (1 << (n + 1)) - 1;
  memset(d, 63, sizeof(d));
  d[0] = 0;
  for (int i = 1; i <= all; i++) {
    int cnt = 0, L;
    for (int k = 0; k <= n; k++)
      if (i >> k & 1) cnt++, L = k;
    if (cnt == 1) {
      if (L == n)
        d[i] = 1;
      else {
        d[i] = calc(L);
        if (d[i] != 1) d[i]++;
      }
      continue;
    }
    if (i == 7) {
      i = i;
    }
    for (int y = (i - 1) & i; y > 0; y = (y - 1) & i) {
      int A = Get(y);
      int B = Get(i ^ y);
      if (y == 3) {
        A = A;
      }
      int k = (a[A] > a[B] ? A : B);
      if (!can(k, y, y ^ i)) continue;
      int CC = cost(A, B);
      if (CC == -(1 << 30)) continue;
      d[i] = min(d[i], d[y] + d[y ^ i] + CC);
    }
  }
  int r = min(d[all], d[(1 << n) - 1]);
  cout << r << endl;
}
