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