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.InputStreamReader;
import java.util.StringTokenizer;

public class E {
	static int range = 10000000;
	static int[] primes;
	static int[] marks;
	static int primeCnt;

	public static void sieve() {
		primes = new int[720000]; // compute as n/ln(n) or slightly more
		primeCnt = 0;
		primes[primeCnt++] = 2;
		int sqrt = (int) (Math.sqrt(range) + 1);
		marks = new int[(int) Math.ceil(range / 64.0)];
		for (int i = 3; i <= sqrt; i += 2) {
			if ((marks[i >> 6] & (1 << ((i >> 1) & 31))) == 0) {
				for (int j = i * i; j <= range; j += (i << 1)) {
					marks[j >> 6] |= (1 << ((j >> 1) & 31));
				}
			}
		}
		for (int i = 3; i <= range; i += 2) {
			if ((marks[i >> 6] & (1 << ((i >> 1) & 31))) == 0) {
				primes[primeCnt++] = i;
			}
		}
	}

	public static void main(String[] args) throws Exception {
		int cnt = nextInt();
		long[] numCount = new long[10000002];
		for (int i = 0; i < cnt; i++) {
			int num = nextInt();
			numCount[1]++;
			numCount[num + 1]--;
		}
		for (int i = 1; i < numCount.length; i++) {
			numCount[i] += numCount[i - 1];
		}
		int[] maxPrimes = new int[10000001];
		sieve();
		loop: for (int i = 2; i <= 10000000; i++) {
			if ((i&1)==1&&(marks[i >> 6] & (1 << ((i >> 1) & 31))) == 0) {
				maxPrimes[i] = i;
				continue;
			}
			int sqrt = (int) Math.sqrt(i) + 1;
			for (int j = 0; primes[j] <= sqrt; j++) {
				if (i % primes[j] == 0) {
					maxPrimes[i] = Math
							.max(primes[j], maxPrimes[i / primes[j]]);
					continue loop;
				}
			}
			maxPrimes[i] = i;
		}
		for (int i = 10000000; i > 1; i--) {
			if (maxPrimes[i] != i) {
				numCount[maxPrimes[i]] += numCount[i];
			}
			numCount[i / maxPrimes[i]] += numCount[i];
		}
		long l = 1, h = 100000000000000l, mid;
		while (l < h) {
			mid = l + (h - l) / 2;
			boolean can = true;
			for (int i = 0; i < primeCnt; i++) {
				if (numCount[primes[i]] == 0)
					continue;
				long howM = 0;
				long tmp = mid;
				long p = primes[i];
				while (tmp >= p) {
					tmp /= p;
					howM += tmp;
				}
				if (howM < numCount[primes[i]]) {
					can = false;
					break;
				}
			}
			if (!can) {
				l = mid + 1;
			} else {
				h = mid;
			}
		}
		System.out.println(l);
	}

	static BufferedReader br = new BufferedReader(new InputStreamReader(
			System.in));
	static StringTokenizer st = new StringTokenizer("");

	static int nextInt() throws Exception {
		return Integer.parseInt(next());
	}

	static String next() throws Exception {
		while (true) {
			if (st.hasMoreTokens()) {
				return st.nextToken();
			}
			String s = br.readLine();
			if (s == null) {
				return null;
			}
			st = new StringTokenizer(s);
		}
	}
}