Any natural number c can be written as power of two natural numbers a and b, i.e. c = ab.

Indeed, a trivial solution is c = c1, 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 = 161 or 42, we wish to write 16 = 24, i.e. a = 2 and b = 4.

Input

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.

Output

For each test case, compute integers a > 0 and b > 0 so that c = ab, 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.