SupCom Problem Solving Challenge Practice Session

In this problem, your task is to compute the decomposition of an integer into prime factors.

Input

The first line of the input contains an integer T denoting the number of test cases. The description of Ttest cases follows. Each test case is described in a single line containing a single integer « n » (1 ≤ n ≤ 10⁶).

Output

For each test case, print in a single line the decomposition of an integer into prime factors as a list of increasing space-separated integers.

Example

Input:
6
16
127
256
513
2048
5097

Output:
2 2 2 2
127
2 2 2 2 2 2 2 2
3 3 3 19
2 2 2 2 2 2 2 2 2 2 2
3 1699