Frankfurt UAS, KMITL, VGU & SPbGUT - Combinatorics & Number Theory

Start

2017-03-26 21:00 AKDT

Frankfurt UAS, KMITL, VGU & SPbGUT - Combinatorics & Number Theory

End

2017-03-30 10:00 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -1667 days 3:13:56

Time elapsed

85:00:00

Time remaining

0:00:00

Problem L
Perfect Pth 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 integer $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 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.

Output

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