Description

“释然、慵懒、尽欢，
时间风干后你与我再无关，
没答案，怎么办，看不惯自我欺瞒。”

灯火阑珊，释然的少年写下了n 个正整数，它们的乘积为p。
月色旖旎，少年忽然想到，如果把p 再乘上一个正整数q 能让它们的积为某个数的阶乘，则称这个数的阶乘为完美阶乘，这个数则为完美数，他厌倦了那些纷扰，只想要知道完美数的最小值，希望你能告诉他。

“灯火阑珊，
我的心借了你的光是明是暗。” ——《小半》

Format

Input

共两行。
第一行一个正整数n。
第二行n 个正整数a[i]，代表少年写下的n 个数。

Output

共一行
一个正整数，代表完美数的最小值。

Sample 1

Input

1
6

Output

3

样例解释：当p=6，q=1 时，p×q=3！

Limitation

1s, 256MiB for each test case.