题目描述

梅森数指形如$2^p-1$的正整数，其中指数$p$是质数。对于一个正整数$p$ （可能不是质数），请判断$2^p-1$是不是质数。如果不是，请将它进行质因数分解。

读入格式

第一行一个正整数$t(1\leq t \leq 30)$，表示数据的组数。

接下来$t$行，每行一个正整数$p(1\leq p \leq 70)$。

输出格式

共$t$行，每行若干正整数，表示每个$p$的质因数分解结果，要求从小到大输出。 如果$2^p-1$是质数，则输出他本身。

样例

样例输入

5
3
6
9
31
59

样例输出

7
3 3 7
7 73
2147483647
179951 3203431780337

备注

以下是测试数据的n的分布，本次作业不限制运行时间，部分数据TLE是可以接受的。

1
n: 2-30
2
n: 31-50
3
n: 51-57
4
n: 55-65，去掉61，62
5
n: 61
6
n: 62
7
n: 67
8
n: 66,68,69,70
9
n: 51-70

29
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30