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$$$。