問題文

最近、そぬけさんはエラトステネスのふるいを勉強しました。
その結果、自然数列 $S_i = i (1 \le i \le 100000)$ を素早く素因数分解することができるようになりました。
しかし、それだけでは面白くないので、少し変わった整数列に対しても素因数分解を試みようと考えました。

初めに、$A_i = i^2 　( 1 \le i \le 100000)$　の素因数分解について考えてみました。そぬけさんはすぐいいアイデアを思いつきました。
次に、　$B_i = i^2-1 ( 1 \le i \le 100000)$　の素因数分解について考えてみました。これも、そぬけさんはすぐに解くことができました。
最後に、$X_i = i^2+1 ( 1 \le i \le$ 100000$100001)$ の素因数分解について考えてみたのですが、

そぬけさんはこの数列の一般項$X_i$は前の二つと違い、きれいに因数分解できない形であることに気づきました。
このままではそぬけさんは$X_i$の値がとても大きくなった時の因数分解ができないので、どう素因数分解すれば良いのか困ってしまいました。
そぬけさんの代わりに$X_i(1 \le i \le$ 100000$100001)$の素因数分解を行ってあげてください。

入力

$Q$
$q_1$
$q_2$
.
.
.
$q_Q$

初めに、前入力の個数$Q$が与えられる。
ここに、$Q$は自然数かつ$1 \le Q \le 100000$をみたす。
その後、続いて$i(1 \le i \le Q)$行にわたって、自然数$q_i(1 \le q_i \le $100000 $100001)$が入力される。
条件に不備がありましたので取り消し線で修正を加えました。申し訳ありません。

出力

$Q$行にわたって出力してください。 $i(1 \le i \le Q)$行目には、$X_{q_i}$の素因数分解の結果を出力してください。
この時、各項の素因数分解の結果は、その数が持つ素因数を重複も含めて小さい順に並べて出力してください。 入出力に関しては、以下の例も参考にしてください。
また、最後に改行してください。

サンプル

8
3
1
4
1
5
9
2
6

2 5
2
17
2
2 13
2 41
5
37

5
8523
6189
6365
1311
37

2 5 13 558781
2 29 660409
2 13 1558201
2 859361
2 5 137

20
40887
72874
61303
51575
67282
63799
77986
73719
58829
55758
29693
85015
65766
31202
47690
25980
91221
41077
83153
79062

2 5 181 923617
5310619877
2 5 13 37 781301
2 2437 545749
5 5 17 1601 6653
2 13 156550477
53 114751249
2 1321 2056961
2 29 29 269 7649
5 621790913
2 5 5 5 41 86017
2 13 4801 57901
51637 83761
5 194712961
3457 657893
17 37 1073069
2 11909 349369
2 5 461 366013
2 5 13 113 470689
5 1250159969