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.

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.

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 |