E. Эзэнт гүрний дайралт

хугацааны хязгаарлалт 5 секунд

санах ойн хязгаарлалт 512 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Холын нэгэн галактикт дайн дахин дэгджээ. Босуулууд эзэнт гүрэн уруу $k$ ширхэг $a_{i}$ хүчээр дайрахаар төлөвлөжээ. Бослогыг дарахын тулд Эзэнт гүрэн шийдвэрлэх тулаанаар дайныг дуусгахаар шийджээ.

Дайныг бүрэн дуусгахын тулд мөргөлдөөний дараах тэнцвэр эерэг бүхэл тоо байх ёстой. Тэнцвэр нь дараах тоогоор илэрхийлэгддэг: $\frac{p}{q}$, энд $p = n!$ ($n$ бол эзэнт гүрний дайралтын хүч) $q=\prod\limits_{i=1}^{k}a_i!$.

Олон жилийн дайн тулааны улмаас эзэнт гүрний нөөц их бага үлджээ. Тиймээс зардал бага гаргахын тулд $n$ хамгийн бага эерэг тоо байх ёстой.

Эзэнт гүрэнд туслан өгөгдсөн энгийн бутархай эерэг бүхэл тоо байхаар хамгийн бага эерэг бүхэл тоог олно уу.

Оролт

Эхний мөрөнд нэг ширхэг бүхэл тоо $k$ $(1 ≤ k ≤ 10^{6})$ өгөгдөнө. 2 дахь мөрөнд $k$ ширхэг бүхэл тоо $a_{1}, a_{2}, ..., a_{k}$ $(1 ≤ a_{i} ≤ 10^{7})$ өгөгдөнө.

Гаралт

Эзэнт гүрнийг ялахад хэрэгтэй хамгийн бага эерэг бүхэл тоо $n$-ийг хэвлэнэ үү.

С++ дээр 64-бит бүхэл тоог унших болон бичихдээ %lld тодорхойлогчийг ашиглахгүй байхыг хүсье. cin, cout streams эсвэл %I64d тодорхойлогчийг ашиглах нь зүйтэй.

Орчуулсан: Энхлут

Жишээ тэстүүд

Оролт
2
1000 1000
Гаралт
2000
Оролт
1
2
Гаралт
2
Сэтгэгдлүүдийг ачааллаж байна...