Migrated from Lutece 982 质因子分解

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

读入一个自然数，将$n$分解为质因子连乘的形式输出。

Input

有多组测试数据。输入的第一行是整数$T$（$0<T\le 10000$），表示测试数据的组数。每一组测试数据只有一行，包含待分解的自然数$n$。该行没有其它多余的符号。$1<n<2^{31}$。

Output

对应每组输入，输出一行分解结果，具体样式参看样例。该行不能有其它多余的符号。

Samples

3
756
2
2093333998

756=2*2*3*3*3*7
2=2
2093333998=2*7*7*17*43*29221

Resources

wxiaoping C语言练习