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.InputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;


public class Main {
	static int MAX = 10000000;
	public static void main(String[] args) {
		int[] F = new int[MAX + 1];
		int[] index = new int[MAX + 1];
		int[] primes = new int[1000000];
		Arrays.fill(F, -1);
		F[0] = 0;
		F[1] = 1;
		for(int i = 2; i * i < F.length; i++)if(F[i] == -1)
		for(int j = i * i; j < F.length; j += i)
			F[j] = i;
		
		int size = 0;
		
		for(int i = 2; i < F.length; i++)if(F[i] == -1){
			F[i] = i;
			index[i] = size;
			primes[size++] = i;
		}
		
		InputReader r = new InputReader(System.in);
		
		int K = r.nextInt();
		
		int[] a = new int[K];
		
		for(int i = 0; i < K; i++)
			a[i] = r.nextInt();
		
		Arrays.sort(a);
		
		int ptr = K - 1;
		
		long[] t = new long[size];
		int mul = 0;
		for(int x = MAX; x >= 1; x--){
			while(ptr >= 0 && x == a[ptr]){mul++; ptr--;}
			if(mul == 0)continue;
			
			int y = x;
			while(y > 1){
				t[index[F[y]]] += mul;
				y /= F[y];
			}
		}
		
		long lo = a[K - 1], hi = 1L << 45;
		for(int i = 0; i < size; i++){
			int p = primes[i];
			
			hi = 1L << 45;
			
			while(lo < hi){
				long md = (lo + hi) >> 1;
				
				long y = p;
				long cnt = 0;
				
				while(md >= y){
					cnt += md / y;
					y *= p;
				}
				
				if(cnt < t[index[p]]){
					lo = md + 1;
				}else{
					hi = md;
				}
			}
		}
		
		System.out.println(lo);
	}
	
	static class InputReader {
	    private BufferedReader reader;
	    private StringTokenizer tokenizer;

	    public InputReader(InputStream stream) {
	        reader = new BufferedReader(new InputStreamReader(stream));
	        tokenizer = null;
	    }

	    public String nextLine(){
	    	try {
				return reader.readLine();
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
				return null;
			}
	    }
	    public String next() {
	        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
	            try {
	                tokenizer = new StringTokenizer(reader.readLine());
	            } catch (IOException e) {
	                throw new RuntimeException(e);
	            }
	        }
	        return tokenizer.nextToken();
	    }

	    public int nextInt() {
	        return Integer.parseInt(next());
	    }
	    public long nextLong() {
	        return Long.parseLong(next());
	    }
	}
}