Множники

Одна з фундаментальних теорем арифметики стверджує, що довільне число більше 1 можна єдиним чином подати у вигляді добутку простих чисел. Порте цей унікальний набір простих множників можна упорядкувати різними способами. Наприклад:

Позначимо через f(k) кількість різних способів упорядкувати прості множники числа k. Тоді f(10) = 2 та f(20) = 3.

Вам задано ціле додтне число n, причому гарантується, что для довільного n завжди існує таке k, що f(k) = n. Знайдіть таке мінімальне k.

Вхідні дані

Вхідні дані містять не більше 1000 тестів, кожен з яких розміщено у окремому рядку. Кожен тест складається з цілого додатного числа n (n < 2^63).

Вихідні дані

Для кожного тесту виведіть число n та найменше k > 1 таке, що f(k) = n. Числа у тестах вибрані таким чином, що k < 2^63.

Приклади