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 maxn = 10000010;
int pre[maxn], n, Max;
vector<int> v;
long long num[maxn];
void initial() {
  Max = -1;
  v.clear();
  memset(num, 0, sizeof(num));
  memset(pre, -1, sizeof(pre));
}
void input() {
  int x;
  for (int i = 0; i < n; i++) {
    scanf("%d", &x);
    Max = max(x, Max);
    num[x]++;
  }
}
bool judge(long long op) {
  for (int i = 0; i < v.size(); i++) {
    long long cnt = 0, tp = op;
    while (tp) {
      cnt = cnt + tp / v[i];
      tp /= v[i];
    }
    if (cnt < num[v[i]]) return false;
  }
  return true;
}
void solve() {
  for (int i = Max - 1; i >= 2; i--) num[i] += num[i + 1];
  for (int i = 2; i <= Max; i++) {
    if (pre[i] == -1) {
      pre[i] = i;
      v.push_back(i);
    }
    for (int j = 0; i * v[j] <= Max; j++) {
      pre[i * v[j]] = v[j];
      if (i % v[j] == 0) break;
    }
  }
  for (int i = Max; i >= 2; i--) {
    if (pre[i] != i) {
      num[pre[i]] += num[i];
      num[i / pre[i]] += num[i];
    }
  }
  long long l = 1, r = 1e18;
  while (l < r) {
    long long mid = (l + r) / 2;
    if (judge(mid))
      r = mid;
    else
      l = mid + 1;
  }
  cout << l << endl;
}
int main() {
  while (scanf("%d", &n) != EOF) {
    initial();
    input();
    solve();
  }
  return 0;
}