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

public class E {

	BufferedReader br;
	PrintWriter out;
	StringTokenizer st;
	boolean eof;

	static final int CNT = 664579;
	static final int N = 10_000_000;

	void solve() throws IOException {
		int[] P = new int[CNT];
		int cnt = 0;

		int[] lp = new int[N + 1];
		Arrays.fill(lp, -1);
		for (int i = 2; i <= N; i++) {
			if (lp[i] == -1) {
				lp[i] = cnt;
				P[cnt++] = i;
			}
			for (int j = 0; j <= lp[i]; j++) {
				int cur = i * P[j];
				if (cur > N)
					break;
				lp[cur] = j;
			}
		}

		int[] times = new int[N + 2];

		int n = nextInt();
		for (int i = 0; i < n; i++) {
			int a = nextInt();
			times[1]++;
			times[a + 1]--;
		}

		for (int i = 1; i <= N; i++)
			times[i] += times[i - 1];

		long[] pow = new long[CNT];
		for (int i = 0; i < CNT; i++) {
			int p = P[i];
			for (long curPow = p; curPow <= N; curPow *= p)
				for (int j = (int) curPow; j <= N; j += curPow)
					pow[i] += times[j];
		}

		long ans = 0;
		for (int i = 0; i < CNT; i++) {
			ans = Math.max(ans, go(P[i], pow[i]));
		}

		out.println(ans);
	}

	long go(int p, long cnt) {
//		System.err.println(p + " " + cnt);
		if (cnt == 0)
			return 1;
		long low = 0; // low! isn't enough
		long high = (long) p * cnt; // high! is enough
		while (low < high - 1) {
			long mid = (low + high) >> 1;
			long tmpMid = mid;
			long curCnt = 0;
			do {
				tmpMid /= p;
				curCnt += tmpMid;
			} while (tmpMid != 0);
			if (curCnt >= cnt)
				high = mid;
			else
				low = mid;
		}
		return high;
	}

	E() throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(System.out);
		solve();
		out.close();
	}

	public static void main(String[] args) throws IOException {
		new E();
	}

	String nextToken() {
		while (st == null || !st.hasMoreTokens()) {
			try {
				st = new StringTokenizer(br.readLine());
			} catch (Exception e) {
				eof = true;
				return null;
			}
		}
		return st.nextToken();
	}

	String nextString() {
		try {
			return br.readLine();
		} catch (IOException e) {
			eof = true;
			return null;
		}
	}

	int nextInt() throws IOException {
		return Integer.parseInt(nextToken());
	}

	long nextLong() throws IOException {
		return Long.parseLong(nextToken());
	}

	double nextDouble() throws IOException {
		return Double.parseDouble(nextToken());
	}
}