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;
int _;
const int MAXN = 10 * 1000 * 1000;
const int MAXK = 1000 * 1000;
int k;
bool prime[MAXN + 1];
int mpd[MAXN + 1];
int a[MAXK + 1];
int sum[MAXN + 1];
long long cnt[MAXN + 1];
long long Num(long long n, long long p) {
  long long ans = 0;
  while (n) {
    n /= p;
    ans += n;
  }
  return ans;
}
int main() {
  for (int i = 2; i <= MAXN; ++i) prime[i] = true;
  for (int i = 2; i * i <= MAXN; ++i) {
    if (prime[i]) {
      for (int j = i * i; j <= MAXN; j += i) {
        if (prime[j]) {
          prime[j] = false;
          mpd[j] = i;
        }
      }
    }
  }
  for (int i = 2; i <= MAXN; ++i)
    if (mpd[i] == 0) mpd[i] = i;
  _ = scanf("%d", &k);
  for (__typeof(k) i = (0); i < (k); ++i) {
    _ = scanf("%d", &a[i]);
    sum[a[i]]++;
  }
  for (int i = MAXN - 1; i >= 2; --i) sum[i] += sum[i + 1];
  for (int i = 2; i <= MAXN; ++i) {
    if (!sum[i]) break;
    int x = i;
    while (x > 1) {
      cnt[mpd[x]] += sum[i];
      x /= mpd[x];
    }
  }
  long long ans = 1;
  for (int i = 2; i <= MAXN; ++i) {
    if (!cnt[i]) continue;
    long long l = 1, r = (long long)MAXN * MAXK;
    while (l != r) {
      long long m = (l + r) / 2;
      if (Num(m, i) >= cnt[i])
        r = m;
      else
        l = m + 1;
    }
    ans = max(ans, l);
  }
  cout << ans << endl;
  return 0;
}