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.
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.
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.