Problem F
Factorizing Large Integers
Time Limit : 15 seconds
 


Given an integer N(≤10^16) 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 ≤10^16).  
     
  Output  
  For every test case output its prime factoring representation. See the sample output for the output format.  
     
  Sample Input Sample Output    
  3
60
36
10007		 60 = 2^2 * 3 * 5
36 = 2^2 * 3^2
10007 = 10007		    
 

Problem Setter: Tasnim Imran Sunny
Special Thanks: Mir Wasi Ahmed
Next Generation Contest 5