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.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;

public class CF300E implements Runnable {
	
	private static final int MAX = 10000001;
	private static final int CNT_PRIMES = 664579;
	
	private int k;
	private int[] a;
	
	private int[] factor;
	
	private int[] primes;
	private long[] count;
	private int[] meet;
	
	@Override
	public void run() {
		InputReader in = new InputReader(System.in);
		k = in.readInt();
		a = new int[k];
		for (int i = 0; i < k; ++i) {
			a[i] = in.readInt();
		}
		factor = new int[MAX];
		meet = new int[MAX];
		Arrays.fill(meet, 0);
		Arrays.sort(a);
		int cur = 0;
		for (int i = 1; i < MAX; ++i) {
			while (cur < k && a[cur] < i) {
				++cur;
			}
			meet[i] = k-cur;
		}
		Arrays.fill(factor, 0);
		int id = 0;
		primes = new int[CNT_PRIMES];
		count = new long[CNT_PRIMES];
		for (int i = 2; i*i < MAX; ++i) {
			if (factor[i] == 0) {
				for (int j = i*i; j < MAX; j += i) {
					factor[j] = i;
				}
			}
		}
		for (int i = 2; i < MAX; ++i) {
			if (factor[i] == 0) {
				primes[id++] = i;
			}
		}
		Arrays.fill(count, 0);
		for (int i = 0; i < CNT_PRIMES; ++i) {
			long cnt = 0;
			int val = primes[i];
			int m = val;
			while (true) {
				int go = val;
				do {
					cnt += meet[go];
					go += val;
				}
				while (go < MAX);
				if (MAX/val < m) {
					break;
				}
				val *= m;
			}
			count[i] = cnt;
		}
		PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
		long lo = 1;
		long hi = 9999998000000L;
		while (lo < hi) {
			long m = (lo + hi) >> 1;
			boolean can = true;
			for (int i = 0; i < CNT_PRIMES; ++i) {
				long cnt = 0;
				int mult = primes[i];
				long val = mult;
				while (true) {
					cnt += m/val;
					if (m/val < mult) {
						break;
					}
					val *= mult;
				}
				if (cnt < count[i]) {
					can = false;
					break;
				}
			}
			if (can) {
				hi = m;
			}
			else {
				lo = m+1;
			}
		}
		out.println(lo);
		out.flush();
	}
	
	private class InputReader {

		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;

		public InputReader(InputStream stream) {
			this.stream = stream;
		}

		public int read() {
			if (numChars == -1)
				throw new InputMismatchException();
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (numChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}

		public int readInt() {
			int c = read();
			while (isWhitespace(c)) {
				c = read();
			}
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9') {
					throw new InputMismatchException();
				}
				res *= 10;
				res += c - '0';
				c = read();
			} 
			while (!isWhitespace(c));
			return res * sgn;
		}

		public boolean isWhitespace(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}
	}

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