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 long long MAXN = 11000000;
long long Max, Cnt[MAXN], Lp[MAXN], P[MAXN], n;
inline long long Read() {
  long long Ret = 0;
  char ch;
  do {
    ch = getchar();
  } while (ch > '9' || ch < '0');
  while (ch >= '0' && ch <= '9') {
    Ret = Ret * 10 + ch - '0';
    ch = getchar();
  }
  return Ret;
}
bool Check(long long a) {
  for (int i = 1; P[i] <= Max && P[i]; ++i) {
    long long s = P[i], Ret = 0;
    for (; s <= a; s *= P[i]) Ret = Ret + a / s;
    if (Ret < Cnt[i]) return 0;
  }
  return 1;
}
int main() {
  n = Read();
  for (int i = 1; i <= n; ++i) {
    long long Val;
    Val = Read();
    Max = max(Max, Val);
    ++Cnt[Val];
  }
  for (long long i = 2; i <= Max; ++i) {
    if (!Lp[i]) {
      Lp[i] = i;
      P[++P[0]] = i;
    }
    for (int j = 1; j <= P[0] && P[j] <= Lp[i] && (long long)i * P[j] <= Max;
         ++j)
      Lp[i * P[j]] = P[j];
  }
  for (long long i = Max; i >= 2; --i) Cnt[i] += Cnt[i + 1];
  for (long long i = Max; i >= 2; --i) {
    if (i != Lp[i]) Cnt[Lp[i]] += Cnt[i];
    Cnt[i / Lp[i]] += Cnt[i];
  }
  for (long long i = 1; i <= P[0]; ++i) Cnt[i] = Cnt[P[i]];
  long long L = 1, R = 10000000000000LL;
  while (L < R) {
    long long Mid = (L + R) >> 1;
    if (Check(Mid))
      R = Mid;
    else
      L = Mid + 1;
  }
  cout << R;
  return 0;
}