B. Математика
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Учитель JATC по математике всегда даёт их классу разные интересные математические задачки, чтобы им не было скучно. Сегодня задачка выглядит следующим образом. Дано целое число $$$n$$$, вы можете выполнить следующие операции ноль или более раз:

  • mul $$$x$$$: умножает $$$n$$$ на $$$x$$$ (где $$$x$$$ является произвольным положительным целым числом).
  • sqrt: заменяет $$$n$$$ на $$$\sqrt{n}$$$ (эту операцию можно выполнить только если $$$\sqrt{n}$$$ является целым числом).

Вы можете выполнять данные операций столько раз, сколько вы хотите. Какого минимального значения $$$n$$$ можно добиться и какое минимальное количество операций нужно сделать, чтобы получить это минимальное значение?

Похоже, что никто в классе не умеет решать эту задачу. Может быть вы можете им помочь?

Входные данные

Единственная строка входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^6$$$) — изначальное значение числа.

Выходные данные

Выведите два целых числа — минимальное значение $$$n$$$, которого можно добиться с помощью операций выше и минимальное требуемое для этого число операций.

Примеры
Входные данные
20
Выходные данные
10 2
Входные данные
5184
Выходные данные
6 4
Примечание

В первом примере можно применить операцию mul $$$5$$$, чтобы получить $$$100$$$, а затем sqrt, чтобы получить $$$10$$$.

Во втором примере можно сначала применить sqrt, чтобы получить $$$72$$$, затем выполнить mul $$$18$$$, чтобы получить $$$1296$$$, и в конце ещё две операции sqrt, чтобы получить $$$6$$$.

Обратите внимание, что не смотря на то, что изначальное значение значение $$$n$$$ не превосходит $$$10^6$$$, оно вполне может становится больше $$$10^6$$$ после выполнения одной или нескольких операций.