## Problem B: Perfect P*th* 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 *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

17
1073741824
25
0

### Output for Sample Input

1
30
2

*G. V. Cormack*