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 CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:16777216")
const string debug_line = "yolo";
const long long linf = 1e15 + 5;
const int BLOCK = 330;
bool isPrime[10000010];
int limitF[10000010];
int count1[10000010];
int index1[10000010];
vector<int> checkP;
long long primeCount[700010];
void calc() {
  for (int(i) = (2); (i) < (10000010); ++(i)) {
    isPrime[i] = true;
  }
  for (int(i) = (10000000); (i) > (-1); --(i)) {
    count1[i] = count1[i + 1] + count1[i];
  }
  cerr << "debug_line"
       << " = " << (debug_line) << endl;
  int countPrimes = 0;
  for (int(i) = (2); (i) < (10000010); ++(i)) {
    if (isPrime[i]) {
      index1[i] = countPrimes;
      countPrimes++;
      for (int j = i; j < 10000010; j = j + i) {
        isPrime[j] = false;
        primeCount[index1[i]] = primeCount[index1[i]] + count1[j];
      }
      long long temp = i * (long long)i;
      while (temp <= 10000010) {
        for (long long j = temp; j < 10000010; j = j + temp) {
          primeCount[index1[i]] += count1[j];
        }
        temp = temp * (long long)i;
      }
      for (int j = i; j < 10000010; j = j + i) {
        limitF[j]++;
      }
      isPrime[i] = true;
    }
  }
  cerr << "countPrimes"
       << " = " << (countPrimes) << endl;
  cerr << "debug_line"
       << " = " << (debug_line) << endl;
  cerr << "debug_line"
       << " = " << (debug_line) << endl;
  cerr << "debug_line"
       << " = " << (debug_line) << endl;
}
bool check1(long long num, long long countPow, long long pnum) {
  long long temp1 = 0;
  long long toMultiply = pnum;
  while (num) {
    num = num / toMultiply;
    temp1 = temp1 + num;
  }
  if (temp1 >= countPow) {
    return true;
  } else {
    return false;
  }
}
bool check(long long num) {
  for (auto &(t1) : (checkP)) {
    {
      if (!check1(num, primeCount[index1[t1]], t1)) {
        return false;
      }
    }
  }
  return true;
}
int main() {
  int n;
  n = 1000000;
  scanf("%d", &n);
  for (int(i) = (0); (i) < (n); ++(i)) {
    int temp;
    temp = n * 10;
    scanf("%d", &temp);
    count1[temp]++;
  }
  calc();
  long long answer1 = 1;
  long long b = 1;
  long long e = 4000000000000000000LL;
  for (int(i) = (2); (i) < (10000010); ++(i)) {
    if (isPrime[i] && primeCount[index1[i]] != 0) {
      checkP.push_back(i);
    }
  }
  for (int(i) = (2); (i) < (10000010); ++(i)) {
    if (isPrime[i] && primeCount[index1[i]] != 0) {
      long long b = 1;
      long long e = 4000000000000000000LL;
      while (b < e) {
        long long mid = (b + e) / 2;
        if (check1(mid, primeCount[index1[i]], i)) {
          e = mid;
        } else {
          b = mid + 1;
        }
      }
      answer1 = max(answer1, e);
    }
  }
  printf("%lld\n", answer1);
  return 0;
}