Surya loves to play with primes. One day, he asked his friend don to print any number in the form of multiple of prime factors. Help don in solving the problem.

Input
The first line will contain an integer t (1<=t<=10^6) denoting number of test case.
For each test case, you will be given an integer n (2<=n<=10^6).

Output
Print a string showing prime factors which should look like :
2^e1 * p2^e2 * .........* pk^ek
where p1, p2, ...., pn are the prime factors and e1, e2, ....., en is the degree of corresponding prime factor.

Note: power of 2 should always be given. For a prime number , only 2^0 is printed.