题目描述

\(n!(n≤10^6)\) 是一个很大的数，对 \(n!\) 进行质因数分解后形式为：\(2^{p1}×3^{p2}×…k^{pk}\)， 其中 \(k\) 为某个质数，\(p_i\) 为对应质数的方幂。编程输出这种形式。

格式

输入格式

第一行为正整数 \(t(≤10)\)，表示数据组数；接下来每行一个正整数 \(n(≤10^6)\)。

输出格式

对于每组数据，输出一行，由若干个以空格隔开的正整数组成，表示 \(n!\) 的质因数分解形式，每个整数表达质数按从小到大的顺序排列后对应的方幂 \(p_i\) (意义见上)。

样例1

样例输入1

2
15
90

样例输出1

11 6 3 2 1 1
86 44 21 13 8 6 5 4 3 3 2 2 2 2 1 1 1 1 1 1 1 1 1 1

样例解释

样例 \(1\) 表示输出表示：\(15!=2^{11}×3^6×5^3×7^2×11^1×13^1\)，这里所有的质数是隐含的，不用输出，且按从小到大的顺序排列。

限制

\(30\%\) 数据中，\(n≤1000\)；
\(60\%\) 数据中，\(n≤100000\)；
\(100\%\) 数据中，\(n≤1000000\)。

来源

地址：芜湖市二十七中电脑班刷题课
作者：汪老师
模拟赛\(T3\)

文件IO

freopen("fact.in","r",stdin);
freopen("fact.out","w",stdout);