我们称$x$为完全平方数，当存在某个整数$b$使得$x = b²$ 。类似地，$x$为完全立方数，当存在某个整数$b$使得$x = b³$ 。更一般地，$x$为完全$p$次幂数，当存在某个整数$b$使得$x = bᵖ$ 。给定一个整数$x$ ，你需要确定最大的$p$ ，使得$x$是完全$p$次幂数。

输入

每个测试用例由包含$x$的一行输入给出。$x$的值绝对值至少为$2$ ，且在$C$、$C++$ 和$Java$中$32$位整数范围内。最后一个测试用例后有一行包含$0$ 。

输出

对于每个测试用例，输出一行，给出使得$x$是完全$p$次幂数的最大整数$p$ 。

输入数据 1

17
1073741824
25
0

输出数据 1

1
30
2

来源

Waterloo local 2004.01.31