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.File;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.StringTokenizer;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main {

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

	BufferedReader in;
	PrintWriter out;
	StringTokenizer st = new StringTokenizer("");

	private void run() throws IOException {
		if (new File("input.txt").exists())
			in = new BufferedReader(new FileReader("input.txt"));
		else
			in = new BufferedReader(new InputStreamReader(System.in));
		if (new File("output.txt").exists())
			out = new PrintWriter("output.txt");
		else
			out = new PrintWriter(System.out);

		solve();

		in.close();
		out.close();
	}

	final int maxn = 1000 * 1000 + 100;
	final int maxp = 10 * 1000 * 1000 + 100;

	int n;
	int a[] = new int[maxn];
	long sum;

	int countPrimes;
	int primes[] = new int[maxp];
	int minDiv[] = new int[maxp];

	int countDiv[] = new int[maxp];
	long powerPrimes[] = new long[maxp];

	void precalc() {
		for (int i = 1; i < maxp; i++)
			minDiv[i] = i;
		countPrimes = 0;
		for (int i = 2; i < maxp; i++) {
			if (minDiv[i] == i)
				primes[countPrimes++] = i;
			for (int j = 0, index; j < countPrimes && primes[j] <= minDiv[i] && (index = primes[j] * i) < maxp; j++)
				minDiv[index] = primes[j];
		}

	}

	long getPowerPrime(long n, long p) {
		long power = 0;
		while (n > 0) {
			n /= p;
			power += n;
		}
		return power;
	}

	long getAnsForPrime(int prime, long power) {
		if (power == 0)
			return 1;

		long l = 1, r = sum;
		while (r - l > 1) {
			long m = (r + l) / 2;
			if (getPowerPrime(m, prime) < power)
				l = m;
			else
				r = m;
		}

		return r;
	}

	void solve() throws IOException {
		precalc();

		n = nextInt();
		fill(countDiv, 0);
		for (int i = 0; i < n; i++) {
			a[i] = nextInt();
			sum += a[i];
			countDiv[a[i]]++;
		}
		
		for (int i = maxp - 2; i >= 0; i--)
			countDiv[i] += countDiv[i + 1];
		
		fill(powerPrimes, 0);
		for (int i = 2; i < maxp; i++) {
			int k = i;
			while (k != 1) {
				powerPrimes[minDiv[k]] += countDiv[i];
				k /= minDiv[k];
			}
		}

		long ans = 0;
		for (int i = 0; i < countPrimes; i++)
			ans = max(ans, getAnsForPrime(primes[i], powerPrimes[primes[i]]));

		out.println(ans);
	}

	String nextLine() throws IOException {
		st = new StringTokenizer("");
		return in.readLine();
	}

	String nextToken() throws IOException {
		while (!st.hasMoreTokens()) {
			st = new StringTokenizer(in.readLine());
		}
		return st.nextToken();
	}

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

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

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

	boolean EOF() throws IOException {
		while (!st.hasMoreTokens()) {
			String str = in.readLine();
			if (str == null)
				return true;
			st = new StringTokenizer(str);
		}
		return false;
	}

}