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.*;
import java.math.*;
import java.security.KeyStore.Entry;
import java.util.*;

public class TestClass {
	private static InputStream stream;
	private static byte[] buf = new byte[1024];
	private static int curChar;
	private static int numChars;
	private static SpaceCharFilter filter;
	private static PrintWriter pw;
	
	private static void soln(){
		int n = nI();
		int arr[] = new int[1+(int)1e6];
		boolean u[] = new boolean[arr.length];
		for(int i=2;i<arr.length;i++){
			if(!u[i]){
				arr[i] = 1;
				for(long j=i*(long)i;j<arr.length;j+=i){
					int jk = (int)j;
					int temp = jk,an=0;
					while(temp%i==0){
						temp/=i;
						an++;
					}
					u[jk] = true;
					arr[jk]+=an;
				}
			}
		}
		HashMap<Long,Long> set[] = new HashMap[n];
		//int fin[] = new int[n];
		//boolean v[] = new boolean[n];
		long in[] = new long[n];
		long ans[] = new long[n];
		for(int i=0;i<n;i++){
			in[i] = nL();
			set[i] = new HashMap<Long,Long>();
		}
		Arrays.sort(in);
		for(int i=0;i<n;i++){
			long tem = in[i];
			for(int j=2;j<arr.length;j++){
				long io = j;
				while(tem%j==0){
					if(set[i].containsKey(io))
						set[i].put(io, set[i].get(io)+1);
					else
						set[i].put(io, (long)1);
					ans[i]+=arr[j];
					//pw.print(tem+" "+io+" ");
					tem/=j;
					if(tem==1)
						break;
				}
				if(tem==1)
					break;
			}
			if(tem!=1)
				set[i].put(tem, (long)1);
			if((in[i]<1e6&&u[(int)in[i]])||in[i]>=1e6)
				ans[i]++;
			if(tem!=1&&tem!=in[i])
				ans[i]++;
			ans[i]=ans[i]<<32|i;
			//pw.println(ans[i]>>32);
		}
		Arrays.sort(ans);
		long nm = 0;
		boolean v = false;
		for(int i=n-1;i>=0;i--){
			boolean w = false;
			for(int j=n-1;j>i;j--){
				boolean n1 = false;
				for(long c:set[(int)ans[i]].keySet()){
					if(set[(int)ans[j]].containsKey(c)&&set[(int)ans[j]].get(c)-set[(int)ans[i]].get(c)>=0);
					else{
						n1 = true;
						break;
					}
				}
				if(!n1){
					for(long c:set[(int)ans[i]].keySet())
						set[(int)ans[j]].put(c, set[(int)ans[j]].get(c)-set[(int)ans[i]].get(c));
					if(ans[i]>>32!=1)
						nm++;
					w = true;
					break;
				}
			}
			if(i==n-1||!w){
				nm+=ans[i]>>32;
				//pw.println(i+" "+(ans[i]>>32));
			}
			if(i!=n-1&&!w)
				v = true;
		}
		if(v)
			nm++;
		pw.println(nm);
	}

	public static void main(String[] args) {
		InputReader(System.in);
		pw = new PrintWriter(System.out);
		soln();
		pw.close();
	}

	// To Get Input
	// Some Buffer Methods
	public static void InputReader(InputStream stream1) {
		stream = stream1;
	}

	private static boolean isWhitespace(int c) {
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}

	private static boolean isEndOfLine(int c) {
		return c == '\n' || c == '\r' || c == -1;
	}

	private static int read() {
		if (numChars == -1)
			throw new InputMismatchException();
		if (curChar >= numChars) {
			curChar = 0;
			try {
				numChars = stream.read(buf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (numChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}

	private static int nI() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int res = 0;
		do {
			if (c < '0' || c > '9')
				throw new InputMismatchException();
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	private static long nL() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		long res = 0;
		do {
			if (c < '0' || c > '9')
				throw new InputMismatchException();
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	private static String nextToken() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isSpaceChar(c));
		return res.toString();
	}

	private static String nLi() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isEndOfLine(c));
		return res.toString();
	}

	private static boolean isSpaceChar(int c) {
		if (filter != null)
			return filter.isSpaceChar(c);
		return isWhitespace(c);
	}

	private interface SpaceCharFilter {
		public boolean isSpaceChar(int ch);
	}
}