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

public class A {
    static MyScanner sc;
    static PrintWriter pw;

    public static void main(String[] args) throws Throwable {
        sc = new MyScanner();
        pw = new PrintWriter(System.out);

        int N = (int) 1e7;
        ArrayList<Integer> primes = new ArrayList<>();
        int[] lp = new int[N + 1];
        for (int i = 2; i <= N; ++i) {
            if (lp[i] == 0) {
                primes.add(i);
                lp[i] = i;
            }
            int curLP = lp[i];
            for (int p : primes)
                if (p > curLP || p * i > N)
                    break;
                else
                    lp[p * i] = i;
        }
        long[] cnt = new long[N + 2];
        int n = sc.nextInt();
        cnt[1] += n;
        while (n-- > 0)
            cnt[sc.nextInt() + 1]--;
        for (int i = 2; i <= N; i++)
            cnt[i] += cnt[i - 1];
        for (int i = N; i >= 2; i--) {
            if (lp[i] != i) {
                cnt[lp[i]] += cnt[i];
                cnt[i / lp[i]] += cnt[i];
                cnt[i] = 0;
            }
        }
        long start = 1, end = (long) 1e13, ans = -1;
        while (start <= end) {
            long mid = (start + end) / 2;
            boolean ok = true;
            for (int i = 2; i <= N; i++)
                if (cnt[i] > 0) {
                    long cnt2 = 0;
                    long p = i;
                    while (p <= mid) {
                        cnt2 += mid / p;
                        if (p > mid / i + 1)
                            break;
                        p *= i;
                    }
                    if (cnt2 < cnt[i]) {
                        ok = false;
                        break;
                    }
                }
            if (ok) {
                ans = mid;
                end = mid - 1;
            } else
                start = mid + 1;
        }
        pw.println(ans);

//        2 *2 * 2* 5 * 5 * 5


        pw.flush();
        pw.close();
    }

    static class MyScanner {
        BufferedReader br;
        StringTokenizer st;

        public MyScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}