Задачі
Maximum Power
Maximum Power
Any natural number \textbf{c} can be written as power of two natural numbers \textbf{a} and \textbf{b}, i.e.
\textbf{c = a^b}.
Indeed, a trivial solution is \textbf{c = c^1}, i.e. \textbf{a = c} and \textbf{b = 1}. Given \textbf{c} ≥ \textbf{2}, your task is to find \textbf{a} and \textbf{b}, so that \textbf{b} is as large as possible. So instead of writing \textbf{16 = 16^1} or \textbf{4^2}, we wish to write \textbf{16 = 2^4}, i.e. \textbf{a = 2} and \textbf{b = 4}.
\InputFile
The first input line contains the number of test cases \textbf{N}, \textbf{1} ≤ \textbf{N} ≤ \textbf{100}.
Each test case consists of a single line with an integer \textbf{c}.
\begin{itemize}
\item \textbf{c} satisfies \textbf{2} ≤ \textbf{c} ≤ \textbf{1000000000}.
\end{itemize}
\OutputFile
For each test case, compute integers \textbf{a} > \textbf{0} and \textbf{b} > \textbf{0} so that \textbf{c = a^b}, and that \textbf{b} is maximum among all possible solutions. The output is formatted as "\textbf{c = a ^ b}", where \textbf{c}, \textbf{a} and \textbf{b} are numerical values. Note the presence of spaces.
Вхідні дані #1
5 16 1000000000 2 2571353 536870912
Вихідні дані #1
16 = 2 ^ 4 1000000000 = 10 ^ 9 2 = 2 ^ 1 2571353 = 137 ^ 3 536870912 = 2 ^ 29