Description

Our math dalao Forsaken likes to "sell weak", which is not a good habit. However, he always gives us some interesting math problems so that we don't get bored. Today the problem is as follows. Given an integer , you can perform the following operations zero or more times:

mul $x$: multiplies $n$ by $x$ (where $x$ is an arbitrary positive integer).

sqrt: replaces $n$ with $\sqrt{n}$ (to apply this operation, $\sqrt{n}$ must be an integer).

You can perform these operations as many times as you like. What is the minimum value of $n$​, that can be achieved and what is the minimum number of operations, to achieve that minimum value?

Format

Input

There are multiply testcases, each testcase contains a single integer $n$ ($1\leqslant n\leqslant10^6$​) — the initial number.

Output

Print two integers: the minimum integer $n$​ that can be achieved using the described operations and the minimum number of operations required.

Samples

20
5184

10 2
6 4

Hints

This is actually an easy problem :**D**
![](http://www.acmicpc.sdnu.edu.cn/uploads/F43F3ECAD54959FCC12F3973640B99F0.jpg)