# Perfect Pth Powers

We say that $x$ is a perfect square if, for some integer $b$, $x = b^{2}$. Similarly, $x$ is a perfect cube if, for some integer $b$, $x = b^{3}$. More generally, $x$ is a perfect $p$th power if, for some integer $b$, $x = b^{p}$. Given an integer $x$ you are to determine the largest integer $p$ such that $x$ is a perfect $p$th power.

## Input

Each test case is given by a line of input containing
$x$. The value of
$x$ will have
*magnitude* at least $2$ and be within the range of a
(32-bit) int in C, C++, and Java. A line containing
$0$ follows the last test
case.

## Output

For each test case, output a line giving the largest integer $p$ such that $x$ is a perfect $p$th power.

Sample Input 1 | Sample Output 1 |
---|---|

17 1073741824 25 0 |
1 30 2 |