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>
const long maxv = 10000001;
bool prime[10000010];
long p[1000010], f[10000010];
long long q[1000010], tq[1000010];
long tot;
long long plus[10000010];
long n;
long long l = 1, r = 1, mid = 0;
bool check(long long x) {
  long long temp;
  for (long i = 0; i < tot; ++i) {
    temp = x;
    tq[i] = 0;
    while (temp) tq[i] += temp = temp / p[i];
    if (tq[i] < q[i]) return false;
  }
  return true;
}
int main() {
  long temp;
  scanf("%d", &n);
  for (long i = 0; i < n; ++i) {
    scanf("%d", &temp);
    r += temp;
    ++plus[temp];
  }
  for (long i = maxv - 1; i > 0; --i) plus[i] += plus[i + 1];
  for (long i = 2; i < maxv; ++i) {
    if (!prime[i]) {
      f[i] = maxv + tot;
      p[tot++] = i;
    }
    for (long j = 0; j < tot; ++j) {
      if (i * p[j] >= maxv) break;
      prime[i * p[j]] = true;
      f[i * p[j]] = p[j];
      if (i % p[j] == 0) break;
    }
  }
  for (long i = maxv - 1; i > 1; --i)
    if (f[i] < maxv) plus[i / f[i]] += plus[i];
  for (long i = 2; i < maxv; ++i)
    if (f[i] >= maxv)
      q[f[i] - maxv] += plus[i];
    else
      q[f[f[i]] - maxv] += plus[i];
  while (r - l > 1) {
    mid = (l + r) / 2;
    if (check(mid))
      r = mid;
    else
      l = mid;
  }
  if (check(l))
    std::cout << l;
  else
    std::cout << r;
  return 0;
}