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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class E {
    
    public static void main(final String[] args) throws IOException, InappropriateDataException {
        try (
                final BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
                final PrintWriter out = new PrintWriter(System.out)
                ) {
            String line;
            for(line = in.readLine(); line != null && !line.isEmpty(); line = in.readLine()) {
                final int n = Integer.parseInt(line);
                line = in.readLine();
                if(line == null) {
                    throw new InappropriateDataException();
                }
                final String[] parts = line.split(" ");
                if(parts.length != n) {
                    throw new InappropriateDataException();
                }
                final Long[] numbers = new Long[n];
                for(int i = 0; i < n; ++i) {
                    numbers[i] = Long.parseLong(parts[i]);
                }
                new Solver(numbers).solve(out);
                out.flush();
            }
        }
    }
    
    private static class Solver {
        private static final int NOT = -1;
        private final Long[] numbers;
        private final int[] numbersFactors;
        private final Integer[][] minNumberVertices;
        private final Integer[][] numberFactorsAfterDivision;
        
        public Solver(final Long[] numbers) {
            final List<Long> numbersList = Arrays.asList((Long[])numbers);
            Collections.shuffle(numbersList);
            this.numbers = numbersList.toArray(numbers);
            Arrays.sort(this.numbers);
            numbersFactors = new int[numbers.length];
            for(int i = 0; i < numbers.length; ++i) {
                numbersFactors[i] = MathUtils.numberFactors(this.numbers[i]);
            }
            minNumberVertices = new Integer[numbers.length + 1][];
            for(int i = 0; i <= numbers.length; ++i) {
                minNumberVertices[i] = new Integer[1 << i];
            }
            numberFactorsAfterDivision = new Integer[numbers.length][];
            for(int i = 0; i < numbers.length; ++i) {
                numberFactorsAfterDivision[i] = new Integer[1 << i];
            }
        }
        
        public void solve(final PrintWriter out) {
            out.println(getMinNumberVertices(0, 0));
        }
        
        private int getMinNumberVertices(final int startIndex, final int madeLeavesMask) {
            Integer result = minNumberVertices[startIndex][madeLeavesMask];
            if(result != null) {
                return result;
            }
            try {
                if(startIndex == numbers.length) {
                    return result = MathUtils.numberBits(madeLeavesMask) > 1 ? 1 : 0;
                }
                result = getMinNumberVertices(startIndex + 1, madeLeavesMask | (1 << startIndex)) + numbersFactors[startIndex] + (numbersFactors[startIndex] > 1 ? 1 : 0);
                for(int subMask = madeLeavesMask; subMask > 0; subMask = (subMask - 1) & madeLeavesMask) {
                    final Integer numberRestFactors = getNumberFactorsAfterDivision(startIndex, subMask);
                    if(numberRestFactors != null) {
                        result = Math.min(result, getMinNumberVertices(startIndex + 1, madeLeavesMask ^ subMask | (1 << startIndex)) + numberRestFactors + 1);
                    }
                }
                return result;
            } finally {
                minNumberVertices[startIndex][madeLeavesMask] = result;
            }
        }
        
        private Integer getNumberFactorsAfterDivision(final int index, final int mask) {
            Integer result = numberFactorsAfterDivision[index][mask];
            if(result != null) {
                return result == NOT ? null : result;
            }
            try {
                long number = numbers[index];
                result = numbersFactors[index];
                for(int i = 0; (1 << i) <= mask; ++i) {
                    if(((mask >> i) & 1) == 1) {
                        final long n = numbers[i];
                        if(number % n > 0) {
                            return result = null;
                        }
                        number /= n;
                        result -= numbersFactors[i];
                    }
                }
                return result;
            } finally {
                numberFactorsAfterDivision[index][mask] = result == null ? NOT : result;
            }
        }
    }
    
    private static class MathUtils {
        
        public static int numberBits(int mask) {
            int result = 0;
            for(; mask > 0; mask = (mask - 1) & mask) {
                ++result;
            }
            return result;
        }
        
        public static int numberFactors(long n) {
            int result = 0;
            for(long i = 2; i * i <= n; ++i) {
                for(; n % i == 0; n /= i) {
                    ++result;
                }
            }
            if(n > 1) {
                ++result;
            }
            return result;
        }
    }
    
    private static class InappropriateDataException extends Exception {
        
    }
    
}
