Maximum Power#3823
Any natural number can be written as power of two natural numbers and , i.e.
Indeed, a trivial solution is c = c^1, i.e. a = c and b = 1. Given c \geq 2, your task is to find and , so that is as large as possible. So instead of writing 16 = 16^1 or 4^2, we wish to write 16 = 2^4, i.e. a = 2 and b = 4.
The first input line contains the number of test cases , 1 \leq N \leq 100.
Each test case consists of a single line with an integer .
satisfies 2 \leq c \leq 1000000000.
For each test case, compute integers a > 0 and b > 0 so that c = a^b, and that is maximum among all possible solutions. The output is formatted as "c = a ^ b", where , and are numerical values. Note the presence of spaces.
Example 1