Q10622: Perfect Pth Powers

我們說 x 是一個完美平方數（perfect square），如果存在某個整數 b 使得 x = b²。同樣的，我們說 x 是一個完美立方數（perfect cube），如果存在某個整數 b 使得 x = b³。更一般來說，x 是一個完美的 p 次方數，如果存在某個整數 b 使得 x = b^p。給你一個整數 x，請你算出最大的 p，使得 x 是一個完美的 p 次方數。

Input

每組測試資料一列，含有1個整數 x。x 的值在C,C++,JAVA中可以32-bit的整數型態來儲存，且絕對值大於1。若 x=0 代表輸入結束。

Output

對每組測試資料輸出一列。算出最大的 p，使得 x 是一個完美的 p 次方數。

17
1073741824
25
-25
64
-64
0

1
30
2
1
6
3