Perfect P-th Power

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$.

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.

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