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:
//package codeforces.archive;

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Problem300E {
    BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    PrintWriter writer = new PrintWriter(new OutputStreamWriter(System.out));

    int[] readInts() throws IOException {
        String line = reader.readLine();
        String []s = line.split(" ");
        int[] ret = new int[s.length];
        for(int i = 0; i < s.length; i++) {
            ret[i] = Integer.parseInt(s[i]);
        }
        return ret;
    }

    int[] tt = null;
    int ti = 0;
    int readInt() throws IOException {
        if(tt == null || ti == tt.length) {
            tt = readInts();
            ti = 0;
        }
        return tt[ti++];
    }

    void solve() throws IOException {
        int mv = 10 * 1000 * 1000 + 1;
        List<Integer> primes = new ArrayList<Integer>();
        int[] mp = new int[mv];
        for(int i = 2; i < mv; i++) {
            if(mp[i] == 0) {
                primes.add(i);
                for(int j = i; j < mv; j += i) {
                    mp[j] = i;
                }
            }
        }
        int n = readInt();
        int[] a = readInts();
        Arrays.sort(a);
        for(int i = 0, j = n - 1; i < j; i++, j--) {
            int t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
        long[] cnt = new long[mv];
        int ix = 0;
        for(int i = a[0]; i > 1; i--) {
            while(ix < n && a[ix] == i) ix++;
            cnt[i] += ix;
            if(mp[i] != i) {
                int p = mp[i];
                cnt[p] += cnt[i];
                cnt[i / p] += cnt[i];
            }
        }
        long lo = 0, hi = (long)n * a[0];
        while(hi - lo > 1) {
            long med = lo + hi >> 1;
            boolean ok = true;
            for(int p : primes) {
                long c = 0;
                for(long i = p; i <= med && i % p == 0; i *= p) {
                    c += med / i;
                }
                if(c < cnt[p]) {
                    ok = false;
                    break;
                }
            }
            if(ok) hi = med;
            else lo = med;
        }
        writer.println(hi);
        writer.flush();
    }

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