题目描述

给定一个整数 $n$ ，你可以进行以下操作零次或多次：

• $mul：$将$n$乘以$x$(其中$x$是一个任意正整数)。
• $sqrt：$将$n$替换为$\sqrt{n}$(要执行此操作，$\sqrt{n}$必须是整数)。

你可以在满足要求的情况下执行这些操作任意次。经过操作，$n$的最小值是多少？

输入格式

输入一行一个整数$n(1 \leq n \leq 10^6 )$，代表初始数字。

输出格式

输出一行两个整数：使用上述操作可以得到的最小整数 $n$和所需的最小运算次数。

样例

20

10 2

5184

6 4

样例解释

在第一个例子中，可以应用$mul$ $5$操作得到$100$，然后应用$sqrt$操作得到$10$。

在第二个示例中，首先应用$sqrt$操作得到$72$，然后应用$mul$ $18$操作得到$1296$，最后再应用两次$sqrt$操作得到$6$。