Problem D
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.

17
1073741824
25
0

1
30
2