Problems
Maximum Power
Maximum Power
Any natural number c can be written as power of two natural numbers a and b, i.e.
c = a^b.
Indeed, a trivial solution is c = c^1, i.e. a = c and b = 1. Given c ≥ 2, your task is to find a and b, so that b 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.
Input data
The first input line contains the number of test cases N, 1 ≤ N ≤ 100.
Each test case consists of a single line with an integer c.
c satisfies 2 ≤ c ≤ 1000000000.
Output data
For each test case, compute integers a > 0 and b > 0 so that c = a^b, and that b is maximum among all possible solutions. The output is formatted as "c = a ^ b", where c, a and b are numerical values. Note the presence of spaces.
Examples
Input example #1
5 16 1000000000 2 2571353 536870912
Output example #1
16 = 2 ^ 4 1000000000 = 10 ^ 9 2 = 2 ^ 1 2571353 = 137 ^ 3 536870912 = 2 ^ 29