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 5Scoring
For all test cases, $1 \le T \le 10^3$, $2 \le N \le 10^{18}$.