Задачі
Множники
Множники
Одна з фундаментальних теорем арифметики стверджує, що довільне число більше \textbf{1} можна єдиним чином подати у вигляді добутку простих чисел. Порте цей унікальний набір простих множників можна упорядкувати різними способами. Наприклад:
Позначимо через \textbf{f(k)} кількість різних способів упорядкувати прості множники числа \textbf{k}. Тоді \textbf{f(10) = 2} та \textbf{f(20) = 3}.
Вам задано ціле додтне число \textbf{n}, причому гарантується, что для довільного \textbf{n} завжди існує таке \textbf{k}, що \textbf{f}(\textbf{k}) =\textbf{ n}. Знайдіть таке мінімальне \textbf{k}.
\InputFile
Вхідні дані містять не більше \textbf{1000} тестів, кожен з яких розміщено у окремому рядку. Кожен тест складається з цілого додатного числа \textbf{n} (\textbf{n} < \textbf{2^63}).
\OutputFile
Для кожного тесту виведіть число \textbf{n} та найменше \textbf{k} > \textbf{1} таке, що \textbf{f(k) = n}. Числа у тестах вибрані таким чином, що \textbf{k} < \textbf{2^63}.
Вхідні дані #1
1 2 3 105
Вихідні дані #1
1 2 2 6 3 12 105 720