题目描述

给定一个正整数 $n$，设 $n = p_1 \times p_2 \times \dots p_k$，其中 $p_i$ 均为质数，对 $1 \leq i < k$，$p_i \leq 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

说明/提示

输入样例 #2

3
9999999967
999966000289
1000000000000

输出样例 #2

9999999967
999983 999983
2 2 2 2 2 2 2 2 2 2 2 2 5 5 5 5 5 5 5 5 5 5 5 5

输入样例 #3

10
190546
832983
24602
152248
854075
35294
777617
984851
856619
248467

输出样例 #3

2 95273
3 17 16333
2 12301
2 2 2 19031
5 5 127 269
2 7 2521
777617
7 7 101 199
839 1021
419 593

数据规模与约定

对全部的测试点，保证 $1 \leq T \leq 10$，$1 < n \leq 10^{12}$。