TRIALDIV - Trial Division


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 ≤ 106).

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

hide comments
rushikeshp825: 2021-07-23 16:25:43

@sapjiv thanks bro , that extra space at the end of line gave me WA .

martian_1: 2020-08-22 20:32:30

i was stucked onthis for quite a long time because of that

martian_1: 2020-08-22 20:31:48

damn ! that trailing space :(

khoaph: 2020-05-04 06:47:41

Be aware of what @sapjv said, thanks!
I got 1 WA because of extra space.

le_hue_369: 2020-03-20 01:37:24

Remembering to put "\n" to begin a new line after each test.

ntnguyen: 2019-12-29 09:57:14

Tks @sapjv!!! :>

sapjv: 2019-09-12 23:44:36

Remember : Don't print any extra space after the output for each number!


Added by:mbk_live
Date:2019-01-08
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:C-CLANG C NCSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG C99 JAVA JULIA PYTHON PYPY3 PYTHON3 SWIFT