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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;


public class E {	
	BufferedReader reader;
    StringTokenizer tokenizer;
    PrintWriter out;
    
    public static int[] generateLargestPrimeFactor(int num) {
        if (num < 0) throw new IllegalArgumentException();
        if (num == 1) return new int[]{0, 1};
        int[] result = new int[num + 1];
        result[0] = 0;
        result[1] = 1;
        for (int i = 2; i * i <= num; i++) {
            if (result[i] == 0) {
                result[i] = i;
                for (int j = i * i; j <= num; j += i) {
                    result[j] = i;
                }
            }
        }
        for (int i = 2; i <= num; i++) 
            if (result[i] == 0)
                result[i] = i;
        return result;
    }
    
    int MAX_A = 10000000;
    
	public void solve() throws IOException {
		int[] lp = generateLargestPrimeFactor(MAX_A);
		int prime_count = 0;
		for(int i = 2; i < MAX_A; i++)
			if( lp[i] == i )
				prime_count++;
		int[] primes = new int[prime_count];
		prime_count = 0;
		for(int i = 2; i < MAX_A; i++){
			if( lp[i] == i )
				primes[ prime_count++ ] = i;
		}
		
		int K = nextInt();
		long right = 0;
		long[] count = new long[MAX_A+1];
		for(int i = 0; i < K; i++){
			int a = nextInt();
			count[ a ]++;
			right += a;
		}
		for(int i = MAX_A-1; i >= 2; i--){
			count[i] += count[i+1];
		}
		for(int i = MAX_A; i >= 2; i--){
			if( lp[i] != i ){
				count[ lp[i] ] += count[i];
				count[ i/ lp[i] ] += count[i];
			}
		}
		
		long left = 1;
		while( left < right ){
			long mid = (left + right) / 2;
			
			boolean OK = true;
			for(int p = 0; p < prime_count; p++){
				int prime = primes[p];
				long tmp = mid;
				long have = 0;
				while( tmp > 0 ){
					have += tmp / prime; 
					tmp /= prime;
				}
				if( have < count[prime] ){
					OK = false;
					break;
				}
			}
			if( !OK ){
				left = mid + 1;
			}
			else{
				right = mid;
			}
		}		
		out.println( left );
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		new E().run();
	}
	
	public void run() {
        try {
            reader = new BufferedReader(new InputStreamReader(System.in));
            tokenizer = null;
            out = new PrintWriter(System.out);
            solve();
            reader.close();
            out.close();
        } catch (Exception e) {
            e.printStackTrace();
            System.exit(1);
        }
    }

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

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

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

    String nextToken() throws IOException {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(reader.readLine());
        }
        return tokenizer.nextToken();
    }

}