Учитель JATC по математике всегда даёт их классу разные интересные математические задачки, чтобы им не было скучно. Сегодня задачка выглядит следующим образом. Дано целое число \(n\), вы можете выполнить следующие операции ноль или более раз:
- mul \(x\): умножает \(n\) на \(x\) (где \(x\) является произвольным положительным целым числом).
- sqrt: заменяет \(n\) на \(\sqrt{n}\) (эту операцию можно выполнить только если \(\sqrt{n}\) является целым числом).
Вы можете выполнять данные операций столько раз, сколько вы хотите. Какого минимального значения \(n\) можно добиться и какое минимальное количество операций нужно сделать, чтобы получить это минимальное значение?
Похоже, что никто в классе не умеет решать эту задачу. Может быть вы можете им помочь?
Выходные данные
Выведите два целых числа — минимальное значение \(n\), которого можно добиться с помощью операций выше и минимальное требуемое для этого число операций.
Примечание
В первом примере можно применить операцию mul \(5\), чтобы получить \(100\), а затем sqrt, чтобы получить \(10\).
Во втором примере можно сначала применить sqrt, чтобы получить \(72\), затем выполнить mul \(18\), чтобы получить \(1296\), и в конце ещё две операции sqrt, чтобы получить \(6\).
Обратите внимание, что не смотря на то, что изначальное значение значение \(n\) не превосходит \(10^6\), оно вполне может становится больше \(10^6\) после выполнения одной или нескольких операций.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
20
|
10 2
|
|
2
|
5184
|
6 4
|