Migrated from Lutece 972 因子分解

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

请写一个程序，读入一个正整数，把它的所有质因子找出来。

Input

本题有多组输入数据。第一行是输入数据的组数$T$，每组数据占一行，有一个要求分解因式的正整数$n$。$1\le T\le 10$，$1\le n\le 10^7$。

Output

对应每组输入数据，输出占一行，注意因子应按质因子的大小从小到大输出。具体见样例。

Samples

1
181944

181944＝2^3*3^2*7*19^2

Resources

wxiaoping 2009年C语言第九次上机