给定一个正整数 $n$， 设 $n = p_1 \times p_2 \times \dots p_k$，其中 $p_i$ 均为质数， 对 $1 \le i < k$, $p_i \le p_{i+1}$。

可以证明，序列$p_i$ 是唯一的。

对每个给定的 $n$，请你求出 $p_1, p_2, \dots p_k$。

输入

第一行是一个整数，表示测试数据组数 $T$。

接下来 $T$ 行，每行一个整数，表示一组数据的 $n$。

输出

对每组数据，输出一行若干个用空格隔开的整数，依次表示 $p_1, p_2, \dots p_k$。

9
2
3
4
5
6
7
8
9
10

2
3
2 2
5
2 3
7
2 2 2
3 3
2 5

数据范围

$T \le 10$ , $0 < n \le 10^{12}$