After watching transformer Harshit came up with his new superhero Optimus Prime . He was so obsessed with his name that he started solving problems related to prime hoping that he will also get super powers as Optimus Prime. But one day he stuck in a problem in finding the prime factorization of any number "N". Can you help out Harshit?

Input:
First line of input contains T - Total no. of test cases
Each test case contains the number "N".

Output:
Output the Prime factorization of number N as shown in the sample output.

Constraints
1<=T<=100
2 <= N <= 10¹²

Problem Setter : Surya Pratap Singh