← 返回题目列表

Codeforces · 1062/B

B. 数学

中文机器翻译题面 查看原题

JATC的数学老师总是给全班同学出一些有趣的数学题,这样他们就不会感到无聊。今天的问题如下。给定一个整数 $$$n$$$,您可以执行以下操作零次或多次:

- mul $$$x$$$:将 $$$n$$$ 乘以 $$$x$$$(其中 $$$x$$$ 是任意正整数)。
- sqrt:用 $$$\sqrt{n}$$$ 替换 $$$n$$$ (要应用此操作,$$$\sqrt{n}$$$ 必须是整数)。

您可以根据需要多次执行这些操作。可以实现的 $$$n$$$ 的最小值是多少?实现该最小值的最少操作次数是多少?

显然,班上没有人知道这个问题的答案,也许你可以帮助他们?

输入

输入的唯一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^6$$$) - 初始数字。

输出

打印两个整数:使用所描述的操作可以实现的最小整数 $$$n$$$ 以及所需的最小操作数。

示例

输入 #1

20

输出 #1

10 2

输入 #2

5184

输出 #2

6 4

注意

在第一个示例中,您可以应用 mul $$$5$$$ 运算得到 $$$100$$$,然后应用 sqrt 得到 $$$10$$$。

在第二个示例中,您可以首先应用 sqrt 得到 $$$72$$$,然后乘以 $$$18$$$ 得到 $$$1296$$$,最后再应用 sqrt 得到 $$$6$$$。

请注意,即使 $$$n$$$ 的初始值小于或等于 $$$10^6$$$,在应用一次或多次操作后它仍然可以变得大于 $$$10^6$$$。