Given an integer $N$, you need to decompose $N$ into a product of primes integers $\prod p_i$.

Input

There are multiple test cases. The first line of the input contains a single integer $T$ ($1 \le T \le 10^3$), indicating the number of test cases.

For each test case, the first line of the input contains a single integer $N$ ($2 \le N \le 10^{18}$).

Output

For each test case, decompose $N$ into a product of several prime integers $N = p_1 \cdot p_2 \cdot \ldots \cdot p_k$ ($p_1 \le p_2 \le \ldots \le p_k$), and output a single line of integers $p_1, p_2, \ldots, p_k$.

Examples

Input

3
2
9
30

Output

2
3 3
2 3 5

Scoring

For all test cases, $1 \le T \le 10^3$, $2 \le N \le 10^{18}$.