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 nmax = 10000111;
long long a[nmax];
int b[nmax];
int k;
int m_num;
int du_max = 0;
long long ans = 1L;
long long soluong(long long u, long long v) {
  if (v == 0) return 0L;
  long long dem = 1LL;
  long long dai = 1LL;
  while (dem * u + 1LL <= v) {
    dem = dem * u + 1LL;
    dai = dai * u;
  }
  return dai * (v / dem) + soluong(u, v - dem * (v / dem));
}
long long phantich(long long u, long long v) { return u * soluong(u, v); }
int main() {
  for (int i = 1; i <= 10000000; i++) {
    a[i] = 0L;
    b[i] = 0;
  }
  cin >> k;
  m_num = 1;
  for (int i = 1; i <= k; i++) {
    int number;
    scanf("%d", &number);
    a[number]++;
    if (number > m_num) m_num = number;
  }
  long long tong = 0L;
  for (int i = m_num; i >= 2; i--) {
    tong += a[i];
    a[i] = tong;
  }
  for (int i = 2; i <= m_num; i++) {
    if (b[i] != 0) continue;
    for (int j = i; j <= m_num / i; j++) {
      if (b[i * j] == 0) b[i * j] = i;
    }
  }
  for (int i = m_num; i >= 2; i--) {
    if (b[i] == 0) continue;
    int num1 = b[i];
    int num2 = i / b[i];
    long long sl = a[i];
    a[i] = 0L;
    a[num1] += sl;
    a[num2] += sl;
  }
  for (int i = 2; i <= m_num; i++) {
    if ((a[i]) == 0L) continue;
    long long kq = phantich((long long)i, a[i]);
    if (kq > ans) ans = kq;
  }
  cout << ans << endl;
  return 0;
}