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

public class Main{

    BufferedReader in;
    StringTokenizer str = null;
    PrintWriter out;

    private String next() throws Exception{
    	if (str == null || !str.hasMoreElements())
    	    str = new StringTokenizer(in.readLine());
    	return str.nextToken();
    }
    
    private int nextInt() throws Exception{
	   return Integer.parseInt(next());
    }
    
    final int MAX = (int)1e7 + 2;

    public void run() throws Exception{
    	in = new BufferedReader(new InputStreamReader(System.in));
    	out = new PrintWriter(System.out);

	    int n = nextInt();
        int a[] = new int[n];
        long r = 1;
        long l = 0;
        for(int i=0;i<n;i++){
            a[i] = nextInt();
            r+=a[i];
        }

        int p[] = new int[MAX];
        p[1] = 1;
        List<Integer> pr = new ArrayList<Integer>();
        
        for(int i=2;i<MAX;i++) {
            if (p[i] == 0) {
                p[i] = i;
                pr.add(i);
            }
            for(int j=0;j<pr.size() && (long)(pr.get(j) * i) < MAX;j++){
                p[i * pr.get(j)] = pr.get(j);
            }
        }

        long []count = new long[MAX];
        for(int i=0;i<n;i++){
            count[a[i]]++;
        }
        for(int i=MAX-2;i>=2;i--){
            count[i]+=count[i+1];
        }

        for(int i=MAX-1;i>=2;i--){
            if (p[i] != i) {
                count[p[i]]+=count[i];
                count[i/p[i]]+=count[i];
            }
        }
        
        /*
        for(int i=2;i<=3;i++){
            System.out.println(i + " " + count[i]);
        }
        */
        
        while(r - l > 1) {
            long m = (r + l)/2;
            boolean ok = true;
            for(int i : pr) {
                long c = 0;
                long x = m;
                while(x > 0) {
                    c+=x/i;
                    x/=i;
                }
                if (c < count[i]) {
                    ok = false;
                    break;
                }
            }
            //System.out.println(m + " " + ok);
            if (ok) {
                r = m;
            }else {
                l = m;
            }
        }

        out.println(r);
        out.close();
    }

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