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 int N = 10000005;
int cnt[N], pn, leastPrime[N], p[1000005];
int n, k, big[N];
long long deg[N];
bool ok(long long x) {
  for (int i = 0; i < pn; ++i) {
    int P = p[i];
    long long cur = P, cnt = 0;
    while (cur <= x) {
      cnt += x / cur;
      cur *= P;
    }
    if (cnt < deg[P]) return false;
  }
  return true;
}
int main() {
  scanf("%d", &n);
  int M = 0;
  long long second = 0;
  for (int i = 0, x; i < n; ++i) {
    scanf("%d", &x);
    second += x;
    cnt[x]++;
    M = max(M, x);
  }
  if (M == 1) {
    puts("1");
    return 0;
  }
  for (int i = M; i > 1; --i) big[i] = big[i + 1] + cnt[i];
  for (int i = 2; i <= M; i += 2) leastPrime[i] = 2;
  for (int i = 3, j; (j = i * i) <= M; i += 2)
    if (!leastPrime[i])
      for (; j <= M; j += (i << 1))
        if (!leastPrime[j]) leastPrime[j] = i;
  p[pn++] = 2;
  for (int i = 3; i <= M; i += 2)
    if (!leastPrime[i]) {
      p[pn++] = i;
      leastPrime[i] = i;
    }
  for (int i = 2; i <= M; ++i) {
    int j = i, t, cnt, k = big[i];
    while (j > 1) {
      t = leastPrime[j];
      cnt = 0;
      while (j % t == 0) {
        j /= t;
        cnt++;
      }
      deg[t] += k * cnt;
    }
  }
  long long l = 0, r = second;
  while (r > l + 1) {
    long long mid = (r + l) >> 1;
    if (ok(mid))
      r = mid;
    else
      l = mid;
  }
  cout << r;
  return 0;
}