Perfect P-th Powers#1208

Perfect P-th Powers

1 second

64 megabytes

Very easy

We say that $x$ is a perfect square if, for some integer $b$ , $x = b^{2}$ x = b^2. Similarly, $x$ is a perfect cube if, for some integer $b$ , $x = b^{3}$ x = b^3. More generally, $x$ is a perfect $p$ -th power if, for some integer $b$ , $x = b^{p}$ x = b^p. Given an integer $x$ , you are to determine the largest $p$ such that $x$ is a perfect $p$ -th power.

Input

Contains one number — a signed $32$ -bit integer $x$ , $∣ x ∣ > 1$ |x| > 1.

Output

Print the largest integer $p$ such that $x$ is a perfect $p$ -th power.

Examples

Example 1

Loading

x = b^{2}

x = b^{3}

x = b^{p}

∣ x ∣ > 1