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.
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.Random;
import java.util.HashSet;
import java.io.OutputStreamWriter;
import java.io.OutputStream;
import java.util.stream.LongStream;
import java.util.Collection;
import java.util.Set;
import java.io.IOException;
import java.io.UncheckedIOException;
import java.util.stream.Stream;
import java.io.Closeable;
import java.io.Writer;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) throws Exception {
        Thread thread = new Thread(null, new TaskAdapter(), "", 1 << 29);
        thread.start();
        thread.join();
    }

    static class TaskAdapter implements Runnable {
        @Override
        public void run() {
            InputStream inputStream = System.in;
            OutputStream outputStream = System.out;
            FastInput in = new FastInput(inputStream);
            FastOutput out = new FastOutput(outputStream);
            CDivisorTree solver = new CDivisorTree();
            solver.solve(1, in, out);
            out.close();
        }
    }

    static class CDivisorTree {
        long best = (long) 1e18;
        long[] a;
        long[] remain;
        long[] divisor;

        public void solve(int testNumber, FastInput in, FastOutput out) {
            int n = in.ri();
            a = in.rl(n);
            Arrays.sort(a);
            SequenceUtils.reverse(a);
            divisor = new long[n];
            remain = new long[n];
            for (int i = 0; i < n; i++) {
                LongFactorization factorization = new LongFactorization(a[i]);
                for (long x : factorization.primes) {
                    long cur = a[i];
                    while (cur % x == 0) {
                        cur /= x;
                        divisor[i]++;
                    }
                }
            }
            int[] p = new int[n];
            dfs(p, 0);
            out.println(best);
        }

        void dfs(int[] p, int i) {
            if (i == p.length) {
                //check;
                System.arraycopy(a, 0, remain, 0, a.length);
                int neg = 0;
                long sum = 0;
                for (int j = 0; j < p.length; j++) {
                    if (p[j] == -1) {
                        neg++;
                        sum += divisor[j];
                    } else {
                        if (remain[p[j]] % a[j] != 0) {
                            return;
                        }
                        remain[p[j]] /= a[j];
                    }
                }
                long cand = p.length + sum;
                if (neg > 1) {
                    cand++;
                }
                for (int j = 0; j < p.length; j++) {
                    if (remain[j] == a[j] && divisor[j] == 1) {
                        cand--;
                    }
                }

                best = Math.min(best, cand);
                return;
            }

            for (int j = -1; j < i; j++) {
                p[i] = j;
                dfs(p, i + 1);
            }
        }

    }

    static class SmallLongModular implements ILongModular {
        long mod;

        public SmallLongModular(long mod) {
            this.mod = mod;
        }

        public long getMod() {
            return mod;
        }

        public long mul(long a, long b) {
            return a * b % mod;
        }

    }

    static class LongModular2305843009213693951 implements ILongModular {
        private static long mod = 2305843009213693951L;
        private static final LongModular2305843009213693951 INSTANCE = new LongModular2305843009213693951();
        private static long mask = (1L << 32) - 1;

        private LongModular2305843009213693951() {
        }

        public static final LongModular2305843009213693951 getInstance() {
            return INSTANCE;
        }

        public long getMod() {
            return mod;
        }

        public long mul(long a, long b) {
            long l1 = a & mask;
            long h1 = (a >> 32) & mask;
            long l2 = b & mask;
            long h2 = (b >> 32) & mask;
            long l = l1 * l2;
            long m = l1 * h2 + l2 * h1;
            long h = h1 * h2;
            long ret = (l & mod) + (l >>> 61) + (h << 3) + (m >>> 29) + ((m << 35) >>> 3) + 1;
            ret = (ret & mod) + (ret >>> 61);
            ret = (ret & mod) + (ret >>> 61);
            return ret - 1;
        }

    }

    static class LongPower {
        final ILongModular modular;

        public LongPower(ILongModular modular) {
            this.modular = modular;
        }

        public long pow(long x, long n) {
            if (n == 0) {
                return 1;
            }
            long r = pow(x, n >> 1);
            r = modular.mul(r, r);
            if ((n & 1) == 1) {
                r = modular.mul(r, x);
            }
            return r;
        }

    }

    static class RandomWrapper {
        private Random random;
        public static final RandomWrapper INSTANCE = new RandomWrapper();

        public RandomWrapper() {
            this(new Random());
        }

        public RandomWrapper(Random random) {
            this.random = random;
        }

        public RandomWrapper(long seed) {
            this(new Random(seed));
        }

        public long nextLong(long n) {
            return Math.round(random.nextDouble() * (n - 1));
        }

    }

    static class GCDs {
        private GCDs() {
        }

        public static long gcd(long a, long b) {
            return a >= b ? gcd0(a, b) : gcd0(b, a);
        }

        private static long gcd0(long a, long b) {
            return b == 0 ? a : gcd0(b, a % b);
        }

    }

    static class FastInput {
        private final InputStream is;
        private byte[] buf = new byte[1 << 13];
        private int bufLen;
        private int bufOffset;
        private int next;

        public FastInput(InputStream is) {
            this.is = is;
        }

        public void populate(long[] data) {
            for (int i = 0; i < data.length; i++) {
                data[i] = readLong();
            }
        }

        private int read() {
            while (bufLen == bufOffset) {
                bufOffset = 0;
                try {
                    bufLen = is.read(buf);
                } catch (IOException e) {
                    bufLen = -1;
                }
                if (bufLen == -1) {
                    return -1;
                }
            }
            return buf[bufOffset++];
        }

        public void skipBlank() {
            while (next >= 0 && next <= 32) {
                next = read();
            }
        }

        public int ri() {
            return readInt();
        }

        public long[] rl(int n) {
            long[] ans = new long[n];
            populate(ans);
            return ans;
        }

        public int readInt() {
            int sign = 1;

            skipBlank();
            if (next == '+' || next == '-') {
                sign = next == '+' ? 1 : -1;
                next = read();
            }

            int val = 0;
            if (sign == 1) {
                while (next >= '0' && next <= '9') {
                    val = val * 10 + next - '0';
                    next = read();
                }
            } else {
                while (next >= '0' && next <= '9') {
                    val = val * 10 - next + '0';
                    next = read();
                }
            }

            return val;
        }

        public long readLong() {
            int sign = 1;

            skipBlank();
            if (next == '+' || next == '-') {
                sign = next == '+' ? 1 : -1;
                next = read();
            }

            long val = 0;
            if (sign == 1) {
                while (next >= '0' && next <= '9') {
                    val = val * 10 + next - '0';
                    next = read();
                }
            } else {
                while (next >= '0' && next <= '9') {
                    val = val * 10 - next + '0';
                    next = read();
                }
            }

            return val;
        }

    }

    static class DigitUtils {
        private DigitUtils() {
        }

        public static long round(double x) {
            if (x >= 0) {
                return (long) (x + 0.5);
            } else {
                return (long) (x - 0.5);
            }
        }

        public static long modplus(long a, long b, long mod) {
            long ans = a + b;
            if (ans >= mod) {
                ans -= mod;
            }
            return ans;
        }

        public static long mod(long x, long mod) {
            if (x < -mod || x >= mod) {
                x %= mod;
            }
            if (x < 0) {
                x += mod;
            }
            return x;
        }

        public static long modmul(long a, long b, long mod) {
            long k = DigitUtils.round((double) a / mod * b);
            return DigitUtils.mod(a * b - k * mod, mod);
        }

    }

    static class LongFactorization {
        public long g;
        public long[] primes;
        int numberOfFactors = -1;

        public LongFactorization(long g) {
            init(g);
        }

        public void init(long g) {
            assert 0 < g && g <= 1e18;
            this.g = g;
            primes = LongPollardRho.findAllFactors(g).stream().mapToLong(Long::valueOf).toArray();
            numberOfFactors = -1;
        }

        public String toString() {
            return g + "=>" + Arrays.toString(primes);
        }

    }

    static class SequenceUtils {
        public static void swap(long[] data, int i, int j) {
            long tmp = data[i];
            data[i] = data[j];
            data[j] = tmp;
        }

        public static void reverse(long[] data) {
            reverse(data, 0, data.length - 1);
        }

        public static void reverse(long[] data, int l, int r) {
            while (l < r) {
                swap(data, l, r);
                l++;
                r--;
            }
        }

    }

    static class FastOutput implements AutoCloseable, Closeable, Appendable {
        private static final int THRESHOLD = 32 << 10;
        private final Writer os;
        private StringBuilder cache = new StringBuilder(THRESHOLD * 2);

        public FastOutput append(CharSequence csq) {
            cache.append(csq);
            return this;
        }

        public FastOutput append(CharSequence csq, int start, int end) {
            cache.append(csq, start, end);
            return this;
        }

        private void afterWrite() {
            if (cache.length() < THRESHOLD) {
                return;
            }
            flush();
        }

        public FastOutput(Writer os) {
            this.os = os;
        }

        public FastOutput(OutputStream os) {
            this(new OutputStreamWriter(os));
        }

        public FastOutput append(char c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput append(long c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput println(long c) {
            return append(c).println();
        }

        public FastOutput println() {
            return append('\n');
        }

        public FastOutput flush() {
            try {
//            boolean success = false;
//            if (stringBuilderValueField != null) {
//                try {
//                    char[] value = (char[]) stringBuilderValueField.get(cache);
//                    os.write(value, 0, cache.length());
//                    success = true;
//                } catch (Exception e) {
//                }
//            }
//            if (!success) {
                os.append(cache);
//            }
                os.flush();
                cache.setLength(0);
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
            return this;
        }

        public void close() {
            flush();
            try {
                os.close();
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
        }

        public String toString() {
            return cache.toString();
        }

    }

    static class LongModularDanger implements ILongModular {
        final long m;

        public long getMod() {
            return m;
        }

        public LongModularDanger(long m) {
            this.m = m;
        }

        public long mul(long a, long b) {
            return DigitUtils.modmul(a, b, m);
        }

    }

    static class LongMillerRabin {
        static ILongModular mod;
        static LongPower power;

        public static boolean mr(long n, int s) {
            if (n <= 1) {
                return false;
            }
            if (n == 2) {
                return true;
            }
            if (n % 2 == 0) {
                return false;
            }
            long m = n - 1;
            while (m % 2 == 0) {
                m /= 2;
            }
            mod = ILongModular.getInstance(n);
            power = new LongPower(mod);
            for (int i = 0; i < s; i++) {
                long x = RandomWrapper.INSTANCE.nextLong(n - 2) + 2;
                if (!mr0(x, n, m)) {
                    return false;
                }
            }
            return true;
        }

        private static boolean mr0(long x, long n, long m) {
            return test(power.pow(x, m), m, n);
        }

        private static boolean test(long y, long exp, long n) {
            long y2 = mod.mul(y, y);
            if (!(exp == n - 1 || test(y2, exp * 2, n))) {
                return false;
            }
            if (exp != n - 1 && y2 != 1) {
                return true;
            }
            if (y != 1 && y != n - 1) {
                return false;
            }
            return true;
        }

    }

    static class LongModular implements ILongModular {
        final long m;

        public long getMod() {
            return m;
        }

        public LongModular(long m) {
            this.m = m;
        }

        public long mul(long a, long b) {
            if (b == 0) {
                return 0;
            }
            long ans = mul(a, b >> 1) << 1;
            if (ans >= m) {
                ans -= m;
            }
            ans += a * (b & 1);
            if (ans >= m) {
                ans -= m;
            }
            return ans;
        }

    }

    static interface ILongModular {
        long getMod();

        default long plus(long a, long b) {
            return DigitUtils.modplus(a, b, getMod());
        }

        long mul(long a, long b);

        static ILongModular getInstance(long mod) {
            if (mod <= Integer.MAX_VALUE) {
                return new SmallLongModular(mod);
            }
            if (mod <= (1L << 50)) {
                return new LongModularDanger(mod);
            }
            if (mod == (1L << 61) - 1) {
                return LongModular2305843009213693951.getInstance();
            }
            return new LongModular(mod);//new BigLongModular(mod);//new LongModular(mod);
        }

    }

    static class LongPollardRho {
        static long[] smallPrimes = new long[]{2, 3, 5, 7, 11, 13, 17, 19};

        public static long findFactor(long n) {
            if (n == 1) {
                return 1;
            }
            if (LongMillerRabin.mr(n, 10)) {
                return n;
            }
            while (true) {
                long f = rho(n);
                if (f != n) {
                    return f;
                }
            }
        }

        public static Set<Long> findAllFactors(long n) {
            if (n == 0) {
                throw new IllegalArgumentException();
            }

            Set<Long> set = new HashSet<>();
            for (long p : smallPrimes) {
                if (n % p != 0) {
                    continue;
                }
                set.add(p);
                while (n % p == 0) {
                    n /= p;
                }
            }
            findAllFactors(set, n);
            return set;
        }

        private static void findAllFactors(Set<Long> set, long n) {
            if (n == 1) {
                return;
            }
            long f = findFactor(n);
            if (f == n) {
                set.add(f);
                return;
            }
            long otherPart = n / f;
//        long g = GCDs.gcd(f, otherPart);
//        while (g != 1) {
//            otherPart /= g;
//            g = GCDs.gcd(f, otherPart);
//        }
            findAllFactors(set, f);
            findAllFactors(set, otherPart);
        }

        private static long rho(long n) {
            if (n % 2 == 0) {
                return 2;
            }
            if (n % 3 == 0) {
                return 3;
            }
            ILongModular modular = ILongModular.getInstance(n);
            long x = 0, y = x, t, q = 1, c = RandomWrapper.INSTANCE.nextLong(n - 1);
            for (int k = 2; ; k <<= 1, y = x, q = 1) {
                for (int i = 1; i <= k; ++i) {
                    x = modular.plus(modular.mul(x, x), c);
                    q = modular.mul(q, Math.abs(x - y));
                    if ((i & 127) == 0) {
                        t = GCDs.gcd(q, n);
                        if (t > 1) {
                            return t;
                        }
                    }
                }
                if ((t = GCDs.gcd(q, n)) > 1) {
                    return t;
                }
            }
        }

    }
}

