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;
mt19937 bruh(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rofl(chrono::steady_clock::now().time_since_epoch().count());
const int N = 1e6 + 200;
const int M = 1e7;
const int mod = 0;
const int inf = 2e9 + 3;
const long long INF = 1e18;
const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
void files() {
  freopen(".in", "r", stdin);
  freopen(".out", "w", stdout);
}
bool p[M + 100];
int n, a[N], was[M + 100], pr[N], sz;
long long col[N];
bool check(long long m) {
  long long x, y;
  for (int i = 1; i <= sz; ++i) {
    x = y = pr[i];
    long long val = col[i];
    while (x <= m) {
      val -= (m / x);
      if (val <= 0) break;
      x *= y;
    }
    if (val > 0) return false;
  }
  return true;
}
int main() {
  for (int i = 2; i <= M; ++i) {
    if (p[i] == 0) {
      pr[++sz] = i;
      for (int j = 2 * i; j <= M; j += i) {
        p[j] = 1;
      }
    }
  }
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    was[a[i]]++;
  }
  for (int i = M; i >= 1; --i) was[i] += was[i + 1];
  long long x, y;
  int pw = 1;
  for (int i = 1; i <= sz; ++i) {
    x = y = pr[i];
    while (x <= M) {
      for (int j = x; j <= M; j += x) col[i] += was[j];
      x *= y;
    }
  }
  long long l = 1, r = 1e13;
  while (l <= r) {
    long long m = (l + r) / 2LL;
    if (check(m))
      r = m - 1;
    else
      l = m + 1;
  }
  cout << r + 1 << '\n';
}