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