Factorizing Large Integers Given an integer N (≤ 1016) find its prime factoring.

Input The first line of the input contains T (≤ 800), the number of test cases. Then the next T lines contains an integer N (1 < N ≤ 1016). Output For every test case output its prime factoring representation. See the sample output for the output format. Sample Input 3 60 36 10007 Sample Output 60 = 2^2 * 3 * 5 36 = 2^2 * 3^2 10007 = 10007