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.