Time Limit: 1 s
Memory Limit: 128 MB

Submission：39
AC：15
Score：99.79

We say that *x* is a perfect square if, for some integer *b*, *x = b ^{2}*. Similarly,

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.

input

17
1073741824
25
0

output

1
30
2