A divisor tree is a rooted tree that meets the following conditions: 

  * Each vertex of the tree contains a positive integer number. 
  * The numbers written in the leaves of the tree are prime numbers. 
  * For any inner vertex, the number within it is equal to the product of the numbers written in its children. 



Manao has n distinct integers a1, a2, ..., an. He tries to build a divisor tree which contains each of these numbers. That is, for each ai, there should be at least one vertex in the tree which contains ai. Manao loves compact style, but his trees are too large. Help Manao determine the minimum possible number of vertices in the divisor tree sought.

Input

The first line contains a single integer n (1 ≤ n ≤ 8). The second line contains n distinct space-separated integers ai (2 ≤ ai ≤ 1012).

Output

Print a single integer — the minimum number of vertices in the divisor tree that contains each of the numbers ai.

Examples

Input

2
6 10


Output

7


Input

4
6 72 8 4


Output

12


Input

1
7


Output

1

Note

Sample 1. The smallest divisor tree looks this way: <image>

Sample 2. In this case you can build the following divisor tree: <image>

Sample 3. Note that the tree can consist of a single vertex.
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
const int UNDEF = -1;
template <typename T>
inline bool chkmax(T &aa, T bb) {
  return aa < bb ? aa = bb, true : false;
}
template <typename T>
inline bool chkmin(T &aa, T bb) {
  return aa > bb ? aa = bb, true : false;
}
const int MAXN = 1e6 + 4;
const int MAXP = MAXN;
bool sieve_array[MAXP + 1];
int ap[MAXP + 1];
vector<int> gpv;
void sieve() {
  for (int i = 0; i <= MAXP; i++) {
    sieve_array[i] = true;
    ap[i] = 1 << 30;
  }
  sieve_array[0] = false;
  sieve_array[1] = false;
  int lim = (int)(ceil(sqrt(MAXP))) + 2;
  for (int i = 2; i <= lim; i++) {
    if (sieve_array[i]) {
      for (int j = i * i; j <= MAXP; j += i) {
        sieve_array[j] = false;
        ap[j] = i;
      }
    }
  }
  for (int i = 2; i <= MAXP; i++) {
    if (sieve_array[i]) {
      gpv.push_back(i);
      ap[i] = i;
    }
  }
}
pair<long long, int> factorize_dest[64];
long long factorize_tmp[64];
map<long long, int> factorize(long long x) {
  int tsz = 0;
  while (x >= MAXP) {
    bool found = false;
    for (auto &p : gpv) {
      if (p * (long long)p > x) break;
      while ((x % p) == 0) {
        x /= p;
        factorize_tmp[tsz++] = p;
        found = true;
      }
    }
    if (x < MAXP) break;
    if (!found) break;
  }
  if (x < MAXP) {
    while (x > 1) {
      int p = ap[x];
      x /= p;
      factorize_tmp[tsz++] = p;
    }
  }
  if (x > 1) factorize_tmp[tsz++] = x;
  sort(factorize_tmp, factorize_tmp + tsz);
  int didx = 0;
  for (int tidx = 0; tidx < tsz; tidx++) {
    long long p = factorize_tmp[tidx];
    if (tidx == 0 || p != factorize_tmp[tidx - 1]) {
      factorize_dest[didx++] = make_pair(p, 1);
    } else
      factorize_dest[didx - 1].second++;
  }
  map<long long, int> h;
  for (int i = 0; i < didx; i++) {
    h[factorize_dest[i].first] = factorize_dest[i].second;
  }
  return h;
}
const int mn = 8;
const int mz = 1 << mn;
long long a[mn];
map<long long, int> vh[mn];
const int INF = 1 << 28;
int gsmin[mz];
int vpc[mz][mn];
int f[mz][mz];
int g[mz][mn];
int final[mz];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  sieve();
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) scanf("%lld", &a[i]);
  int zlim = 1 << n;
  sort(a, a + n);
  for (int r = 0; r < n; r++) {
    vh[r] = factorize(a[r]);
    int got = 0;
    for (auto &w : vh[r]) got += w.second;
  }
  for (int now = 0; now < zlim; now++) {
    map<long long, int> hnow;
    for (int r = 0; r < n; r++) {
      if (now & (1 << r)) {
        for (auto &w : vh[r]) hnow[w.first] += w.second;
      }
    }
    for (int r = 0; r < n; r++) {
      map<long long, int> hs = vh[r];
      for (auto &w : hnow) hs[w.first] -= w.second;
      int cost = 0;
      for (auto &w : hs) {
        if (w.second < 0) {
          cost = INF;
          break;
        }
        cost += w.second;
      }
      vpc[now][r] = cost;
    }
  }
  for (int now = 0; now < zlim; now++) {
    for (int r = 0; r < n; r++) {
      g[now][r] = INF;
    }
  }
  for (int r = 0; r < n; r++) {
    int ans = vpc[0][r];
    if (ans > 1) ans++;
    g[1 << r][r] = ans;
  }
  for (int z = 0; z < zlim; z++)
    for (int y = 0; y < zlim; y++) f[z][y] = INF;
  f[0][0] = 0;
  for (int seen = 1; seen < zlim; seen++) {
    for (int now = 0; (now = (now - (seen)) & (seen));) {
      int best = INF;
      for (int cseen = 0; (cseen = (cseen - (seen)) & (seen));) {
        for (int r = 0; r < n; r++) {
          int rmsk = 1 << r;
          if ((rmsk & now) != 0 && (rmsk & cseen) != 0) {
            int prev = f[seen ^ cseen][now ^ (1 << r)];
            int cost = g[cseen][r];
            int cand = prev + cost;
            if (cand < best) {
              best = cand;
            }
          }
        }
      }
      best++;
      for (int r = 0; r < n; r++) {
        if ((1 << r) == now) {
          chkmin(best, g[seen][r]);
        }
      }
      f[seen][now] = best;
      if (best < INF) {
        for (int r = 0; r < n; r++) {
          {
            int pcost = vpc[now][r];
            int ans = pcost + best;
            if (pcost > 0) ans++;
            if (pcost < INF) {
              chkmin(g[seen | (1 << r)][r], ans);
            }
          }
        }
      }
    }
  }
  for (int seen = 0; seen < zlim; seen++) {
    int best = INF;
    for (int r = 0; r < n; r++) {
      chkmin(best, g[seen][r]);
    }
    gsmin[seen] = best;
  }
  final[0] = 0;
  for (int z = 1; z < zlim; z++) {
    int best = INF;
    for (int seen = 0; seen = seen - z & z;) {
      chkmin(best, final[z ^ seen] + gsmin[seen]);
    }
    final[z] = best;
  }
  int last = min(final[zlim - 1] + 1, gsmin[zlim - 1]);
  printf("%d\n", last);
}
