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;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class ProblemE {
	
	static int[] div;
	
	static boolean[] sievePrimes(int n) {
		boolean[] isp = new boolean[n+1];
		div = new int[n+1];
		Arrays.fill(div, Integer.MAX_VALUE);
		Arrays.fill(isp, true);
		isp[1] = false;
		for (int i = 2 ; i <= n ; i++) {
			if (isp[i]) {
				div[i] = i;
				for (long ii = 1L * i * i ; ii <= n ; ii += i) {
					isp[(int)ii] = false;
					div[(int)ii] = Math.min(div[(int)ii], i);
				}
			}
		}
		return isp;
	}
	
	static int[] generatePrimes(int n, boolean[] isp) {
		int[] ret = new int[1000000];
		int pidx = 0;
		for (int i = 1 ; i <= n ; i++) {
			if (isp[i]) {
				ret[pidx++] = i;
			}
		}
		return ret;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter out = new PrintWriter(System.out);
		boolean[] isp = sievePrimes(10000000);
		int[] ps = generatePrimes(10000000, isp);
		int[] pmap = new int[10000001];
		Arrays.fill(pmap, -1);
		int pl = ps.length;
		for (int i = 0 ; i < pl ; i++) {
			pmap[ps[i]] = i;
		}

		int k = Integer.valueOf(in.readLine());
		String[] pi = in.readLine().split(" ");
		long[] dp = new long[10000010];
		for (int i = 0 ; i < k ; i++) {
			dp[1]++;
			dp[Integer.valueOf(pi[i])+1]--;
		}
		for (int ai = 2 ; ai <= 10000000 ; ai++) {
			dp[ai] += dp[ai-1];
		}
		for (int ai = 10000000 ; ai >= 2 ; ai--) {
			long v = dp[ai];
			dp[ai] = 0;
			dp[div[ai]] += v;
			if (ai > div[ai]) {
				dp[ai/div[ai]] += v;
			}
		}
		
		long[] denom = new long[pl];
		for (int i = 0 ; i < pl ; i++) {
			denom[i] = dp[ps[i]];
		}
		
		long lo = Integer.valueOf(pi[0])-1;
		long up = 10000000000000L;
		while (up - lo > 1) {
			long med = (lo + up) / 2;
			if (isvalid(med, denom, ps)) {
				up = med;
			} else {
				lo = med;
			}
		}
		out.println(up);
		out.flush();
	}
	

	private static boolean isvalid(long med, long[] denom, int[] ps) {
		int pl = ps.length;
		for (int j = 0 ; j < pl ; j++) {
			if (ps[j] == 0) {
				break;
			}
			long cnt = 0;
			if (med >= ps[j]) {
				long ii = med;
				while (ii >= 1) {
					ii /= ps[j];
					cnt += ii;
				}
				if (cnt < denom[j]) {
					return false;
				}
			} else {
				break;
			}
		}
		return true;
	}

	public static void debug(Object... o) {
		System.err.println(Arrays.deepToString(o));
	}
}