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 static java.lang.Math.max;

import java.io.*;
import java.util.*;

public class E {

    static void solve() throws IOException {
        int k = nextInt();
        int[] a = new int[k];
        for (int i = 0; i < k; i++) {
            a[i] = nextInt();
        }
        int maxValue = 0;
        for (int value : a) {
            maxValue = max(maxValue, value);
        }
        int[] primes = calcP(maxValue + 1);


        int[] count = new int[maxValue + 1];
        for (int value : a) {
            ++count[value];
        }
        for (int i = maxValue; i > 0; --i) {
            count[i - 1] += count[i];
        }

        long[] degInFact = new long[primes.length];

        for (int primeIndex = 0; primeIndex < primes.length; ++primeIndex) {
            int prime = primes[primeIndex];
            while (true) {
                for (int i = prime; i <= maxValue; i += prime) {
                    degInFact[primeIndex] += count[i];
                }
                long next = (long) prime * primes[primeIndex];
                if (next > maxValue) {
                    break;
                }
                prime = (int) next;
            }
        }
        
        long minN = 0;
        long maxN = Long.MAX_VALUE;

        while (maxN > minN + 1) {
            long midN = maxN + minN >>> 1;
            if (largeEnough(midN, primes, degInFact)) {
                maxN = midN;
            } else {
                minN = midN;
            }
        }
        out.println(maxN);
    }

    static int[] calcP(int max) {
        boolean[] notPrime = new boolean[max];
        notPrime[0] = notPrime[1] = true;
        for (int i = 2; i * i < max; i++) {
            if (!notPrime[i]) {
                for (int j = i * i; j < max; j += i) {
                    notPrime[j] = true;
                }
            }
        }
        int cnt = 0;
        for (int i = 0; i < max; i++) {
            if (!notPrime[i])
                cnt++;
        }
        int[] p = new int[cnt];
        cnt = 0;
        for (int i = 0; i < max; i++) {
            if (!notPrime[i])
                p[cnt++] = i;
        }
        return p;
    }

    private static boolean largeEnough(long checkN, int[] primes,
            long[] degInFact) {
        for (int primeIndex = 0; primeIndex < primes.length; primeIndex++) {
            int prime = primes[primeIndex];
            long pow = degInFact[primeIndex];
            long val = checkN;
            for (val /= prime; val > 0 && pow > 0; val /= prime) {
                pow -= val;
            }
            if (pow > 0) {
                return false;
            }
        }
        return true;
    }

    static BufferedReader br;
    static StringTokenizer st;
    static PrintWriter out;

    public static void main(String[] args) throws IOException {
        InputStream input = System.in;
        PrintStream output = System.out;
        File file = new File("e.in");
        if (file.exists() && file.canRead()) {
            input = new FileInputStream(file);
        }
        br = new BufferedReader(new InputStreamReader(input));
        out = new PrintWriter(output);
        solve();
        out.close();
    }

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

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

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

    static String nextToken() throws IOException {
        while (st == null || !st.hasMoreTokens()) {
            String line = br.readLine();
            if (line == null) {
                return null;
            }
            st = new StringTokenizer(line);
        }
        return st.nextToken();
    }
}