Oh no! Phoenix1369 is taking ICS this semester and once again, he has left his homework to the last minute. Luckily, it only consisted of one question:

Given a list of natural numbers, output the prime factorization of each number.

Unfortunately, he was too busy typing up this problem statement to do it.

Would you write a program that does his homework for him? As compensation, he will gladly reward you with five points.

Input Specification

The input begins with an integer ~N~, where ~1 \le N \le 1000~, indicating the number of lines to follow.
The next ~N~ lines will each contain a test case in the form of a single natural number ~M~, where ~2 \le M \le 10^7~.

Output Specification

For each integer ~M~, your program should output the prime factorization of ~M~ on a single line, separated with single spaces and sorted in non-decreasing order.

Sample Input

5
3
13
42
666
1369

Sample Output

3
13
2 3 7
2 3 3 37
37 37