**Description **

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 pth power if, for
some integer b, x = b^{p}. Given an integer x
you are to determine the largest 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 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 **

`17`

`1073741824`

`25`

`0`

**Sample Output **

`1`

`30`

`2`

**Source **