Prime Factorization

题目描述

求正整数的质因数分解.

输入格式

输入共有 n + 1 行.

第 1 行为一个正整数 n.

接下来的 n 行, 每行为一个待分解的正整数 A.

输出格式

输出共有 n 行, 每行为若干个正整数, 分别对应 A 的由小到大排列的所有质因数. 质因数出现的次数为质因数分解中该质因数对应的指数次数.

样例

下面的样例为第一个测试点.

样例输入

10
5577
9883
5686
1385
3995
3912
5793
4265
3283
4129

样例输出

3 11 13 13
9883
2 2843
5 277
5 17 47
2 2 2 3 163
3 1931
5 853
7 7 67
4129

说明

• n <= 10^4
• A <= 10^9