eolymp
bolt
Try our new interface for solving problems
Problems

Maximum Power

Maximum Power

Time limit 1 second
Memory limit 64 MiB

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 c2, 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, 1N100.

Each test case consists of a single line with an integer c.

  • c satisfies 2c1000000000.

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
Source University of Toronto 2010 ACM Tryout: Saturday, October 2, 2010