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>
const int N = 10000000;
int divisor[N + 1];
std::vector<int> primes;
long long count[N + 1];
long long test(long long n, int p) {
  long long ret = 0;
  for (long long i = p; i <= n; i *= p) {
    ret += n / i;
  }
  return ret;
}
int main() {
  memset(divisor, -1, sizeof(divisor));
  for (int i = 2; i <= N; ++i) {
    if (divisor[i] == -1) {
      primes.push_back(i);
    }
    for (int k = 0; k < (int)primes.size() && i * primes[k] <= N; ++k) {
      divisor[i * primes[k]] = primes[k];
      if (i % primes[k] == 0) {
        break;
      }
    }
  }
  memset(count, 0, sizeof(count));
  int m;
  scanf("%d", &m);
  while (m--) {
    int a;
    scanf("%d", &a);
    count[a]++;
  }
  for (int i = N; i >= 2; --i) {
    count[i - 1] += count[i];
  }
  for (int i = N; i >= 2; --i) {
    if (divisor[i] != -1) {
      count[divisor[i]] += count[i];
      count[i / divisor[i]] += count[i];
      count[i] = 0;
    }
  }
  long long answer = 1;
  for (int i = 2; i <= N; ++i) {
    if (divisor[i] == -1) {
      long long low = 0;
      long long high = 1000000000000000000LL;
      while (low < high) {
        long long middle = low + high >> 1;
        if (test(middle, i) >= count[i]) {
          high = middle;
        } else {
          low = middle + 1;
        }
      }
      answer = std::max(answer, high);
    }
  }
  std::cout << answer << std::endl;
}