Perfect P-th Power

Time limit1sMemory limit128 MB

Summary

For each nonzero integer x, find the largest exponent p such that x equals some integer raised to the p-th power.

Level: Medium5 of 10
Topics: Number theory, Math, Binary search
Solved: No attempts yet

Problem

For an integer $b$ , if $x$ can be written as $x = b^2$ then $x$ is called a perfect square, and if $x = b^3$ then $x$ is called a perfect cube. In general, if $x = b^p$ for some integer $b$ , then $x$ is called a perfect $p$ -th power.

Given an integer $x$ , write a program that finds the largest integer $p$ for which there exists an integer $b$ with $x = b^p$ .

Input

The input consists of several test cases. Each test case is a single line containing one integer $x$ . Here $|x| \ge 2$ , and $x$ lies within the signed 32-bit integer range, i.e. $-2147483648 \le x \le 2147483647$ .

The line after the last test case contains a single $0$ , which is not processed and marks the end of input.

Output

For each test case, print on its own line the largest integer $p$ for which there exists an integer $b$ with $x = b^p$ .

Examples2

Example 1
Input
```
17
1073741824
25
0
```
Expected output
```
1
30
2
```
Example 2
Input
```
-8
-27
-32
0
```
Expected output
```
3
3
5
```