Problem: In a far away galaxy there is war again. The treacherous Republic made k precision strikes of power ai on the Empire possessions. To cope with the republican threat, the Supreme Council decided to deal a decisive blow to the enemy forces. 

To successfully complete the conflict, the confrontation balance after the blow should be a positive integer. The balance of confrontation is a number that looks like <image>, where p = n! (n is the power of the Imperial strike), <image>. After many years of war the Empire's resources are low. So to reduce the costs, n should be a minimum positive integer that is approved by the commanders.

Help the Empire, find the minimum positive integer n, where the described fraction is a positive integer.

Input

The first line contains integer k (1 ≤ k ≤ 106). The second line contains k integers a1, a2, ..., ak (1 ≤ ai ≤ 107).

Output

Print the minimum positive integer n, needed for the Empire to win.

Please, do not use the %lld to read or write 64-but integers in С++. It is preferred to use the cin, cout streams or the %I64d specificator.

Examples

Input

2
1000 1000


Output

2000

Input

1
2


Output

2

Solution (in JAVA):

Solution:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class EmpireStrikesBack {
	
	private static long[] inp;
	private static int[] pri;
	private static int count = 0;
	
	public static long q(long x, long p) {
		long res = 0;
		while(x >= p) {
			res += x/p;
			x /= p;
		}
		return res;
	}
	
	public static boolean check(long n) {
		for(int i = 0; i < count; i++) {
			if(q(n, pri[i]) < inp[pri[i]]) {
				return false;
			}
		}
		return true;
	}
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		int up = 10000001;
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		String line = bf.readLine();
		int k = Integer.parseInt(line);
		int[] a = new int[k];   long[] num = new long[up];
		pri = new int[up];   int[] check = new int[up];
		inp = new long[up];  int ind = 0;
		long sum = 0;   int max = 0;
		for(int i = 1; i < up; i++) {
			num[i] = 0;   check[i] = 0;   inp[i] = 0;
		}
		line = bf.readLine();
		for (String numStr: line.split(" ")) {
		    a[ind]= Integer.parseInt(numStr);
		    sum += a[ind];
			max = Math.max(max, a[ind]);
			num[a[ind++]]++;
		}
		for(int i = max - 1; i >= 2; i--) {
			num[i] += num[i + 1];
		}
		for(int i = 2; i <= max; i++) {
			if(check[i] == 0) {
				pri[count++] = i;
				for(int j = i; j <= max; j += i)
					check[j] = i;
			}
		}
		for(int i = max; i >= 2; i--) {
			inp[check[i]] += num[i];
			num[i/check[i]] += num[i];
		}
		long lo = max, hi = sum;
		while(lo < hi) {
			long n = (lo + hi)/2;
			if(check(n))
				hi = n;
			else
				lo = n + 1;
		}
		System.out.println(lo);
	}

}