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;
const long long MAXN = 10000002;
long long primes[MAXN], nprm;
long long lp[MAXN];
void criba(int n) {
  nprm = 0;
  primes[nprm++] = 2;
  lp[2] = 2;
  for (int i = 2; i * 2 <= n; i++) {
    lp[i * 2] = 2;
  }
  int i = 3;
  for (; i * i <= n; i += 2) {
    if (!lp[i]) {
      primes[nprm++] = i;
      lp[i] = i;
      for (int j = i; j * i <= n; j += 2) {
        lp[j * i] = i;
      }
    }
  }
  for (; i <= n; i += 2) {
    if (!lp[i]) {
      primes[nprm++] = i;
      lp[i] = i;
    }
  }
}
long long ex[MAXN];
long long calc(long long p, long long num) {
  long long s = 0ll;
  long long pp = p;
  while (pp <= num) {
    s += num / pp;
    pp *= p;
  }
  return s;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  criba(MAXN - 2ll);
  long long k;
  cin >> k;
  long long n = 1ll;
  long long s = 0ll;
  for (long long i = 0ll; i < k; i++) {
    long long x;
    cin >> x;
    ex[x]++;
    s += x;
  }
  for (long long i = MAXN - 2ll; i >= 2ll; i--) {
    ex[i] += ex[i + 1ll];
  }
  for (long long i = MAXN - 2ll; i >= 2ll; i--) {
    if (lp[i] != i) {
      ex[lp[i]] += ex[i];
      ex[i / lp[i]] += ex[i];
    }
  }
  for (long long i = 0ll; i < nprm; i++) {
    long long p = primes[i];
    long long exp = ex[p];
    if (!ex[p]) {
      continue;
    }
    long long ini = 1ll;
    long long fin = exp * p;
    long long tmp = n;
    while (ini <= fin) {
      long long mid = (ini + fin) / 2ll;
      if (calc(p, mid) >= exp) {
        tmp = mid;
        fin = mid - 1ll;
      } else {
        ini = mid + 1ll;
      }
    }
    n = max(n, tmp);
  }
  cout << n << '\n';
}