We say that \textbf{x} is a perfect square if, for some integer \textbf{b}, \textbf{x} = \textbf{b^2}. Similarly, \textbf{x} is a perfect cube if, for some integer \textbf{b}, \textbf{x} = \textbf{b^3}. More generally, \textbf{x} is a perfect \textbf{p}th power if, for some integer \textbf{b}, \textbf{x} = \textbf{b^p}. Given an integer \textbf{x} you are to determine the largest \textbf{p} such that \textbf{x} is a perfect \textbf{p}th power. \InputFile Contains one number \textbf{-} a signed 32-bit integer \textbf{x}, |\textbf{x}| > \textbf{1}. \OutputFile Print the largest integer \textbf{p} such that \textbf{x} is a perfect \textbf{p}th power.