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