Prime Factorization

View as PDF

Submit solution

Points: 7
Time limit: 1.0s
Memory limit: 128M

Problem type
Allowed languages

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 seven 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 testcase 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


Sample Output

2 3 7
2 3 3 37
37 37


There are no comments at the moment.