Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

E. Empire Strikes Back

time limit per test

5 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputIn a far away galaxy there is war again. The treacherous Republic made *k* precision strikes of power *a*_{i} 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 , where *p* = *n*! (*n* is the power of the Imperial strike), . 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* ≤ 10^{6}). The second line contains *k* integers *a*_{1}, *a*_{2}, ..., *a*_{k} (1 ≤ *a*_{i} ≤ 10^{7}).

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

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/30/2017 04:11:00 (c4).

Desktop version, switch to mobile version.
User lists

Name |
---|