Танд $n$ тоо өгөгдсөн бол уг тооны анхны тоон задаргааг хэвлэ.

$a_k$ анхны тоо байхаар $n$ тоо нь $n = a_1^{b_1} a_2^{b_2} ... a_k^{b_k}$ ($b_i > 0$) хэлбэртэй бичигддэг бол таны програм $a_1...a_1a_2...a_2...a_k...*a_k$ хэлбэрийн гаралт гаргах ёстой. Энд үржигдэхүүнүүд үл буурах эрэмбэтэй, $a_i$ үржигдэхүүн болгон $b_i$ удаа хэвлэгдсэн байх юм.

Оролт

$n$ ($2 ≤ n ≤ 10000$) тоо өгөгдөнө.

Гаралт

Дээр дурьдсанчлан $n$ тооны анхны тоон задаргааг хэвлэ.