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:
// practice with rainboy
import java.io.*;
import java.util.*;

public class CF300E extends PrintWriter {
	CF300E() { super(System.out, true); }
	static class Scanner {
		Scanner(InputStream in) { this.in = in; } InputStream in;
		int k, l; byte[] bb = new byte[1 << 15];
		byte getc() {
			if (k >= l) {
				k = 0;
				try { l = in.read(bb); } catch (IOException e) { l = 0; }
				if (l <= 0) return -1;
			}
			return bb[k++];
		}
		int nextInt() {
			byte c = 0; while (c <= 32) c = getc();
			int a = 0;
			while (c > 32) { a = a * 10 + c - '0'; c = getc(); }
			return a;
		}
	}
	Scanner sc = new Scanner(System.in);
	public static void main(String[] $) {
		CF300E o = new CF300E(); o.main(); o.flush();
	}

	Random rand = new Random();
	void sort(int[] aa, int n) {
		for (int i = 1; i < n; i++) {
			int j = rand.nextInt(i + 1);
			int tmp = aa[i]; aa[i] = aa[j]; aa[j] = tmp;
		}
		Arrays.sort(aa, 0, n);
	}
	static final int A = 10000000;
	long count(int p, long x) {
		return x < p ? 0 : x / p + count(p, x / p);
	}
	void main() {
		int n = sc.nextInt();
		int[] aa = new int[n];
		for (int i = 0; i < n; i++)
			aa[i] = sc.nextInt();
		sort(aa, n);
		int[] kk = new int[A + 1];
		for (int i = 0, j, k = n, b = 0; i < n; i = j) {
			int a = aa[i];
			j = i + 1;
			while (j < n && aa[j] == a)
				j++;
			while (b < a)
				kk[++b] = k;
			k -= j - i;
		}
		long[] ll = new long[A + 1];
		boolean[] composite = new boolean[A + 1];
		int cnt = 0;
		for (int a = 2; a <= A; a++) {
			if (composite[a])
				continue;
			cnt++;
			for (int b = a; b <= A; b += a) {
				composite[b] = true;
				int k = 0;
				for (int c = b; c % a == 0; c /= a)
					k++;
				ll[a] += kk[b] * k;
			}
		}
		int[] pp = new int[cnt];
		cnt = 0;
		for (int a = 2; a <= A; a++)
			if (ll[a] != 0) {
				pp[cnt] = a;
				ll[cnt] = ll[a];
				cnt++;
			}
		long lower = 0, upper = (long) A * n;
		while (upper - lower > 1) {
			long x = (lower + upper) / 2;
			boolean yes = true;
			for (int h = 0; h < cnt; h++)
				if (count(pp[h], x) < ll[h]) {
					yes = false;
					break;
				}
			if (yes)
				upper = x;
			else
				lower = x;
		}
		println(upper);
	}
}