假设x是一个正整数，它的值不超过65535(即1<x<=65535)，请编写一个程序，将x分解为若干个素数的乘积。

Input

输入的第一行含一个正整数k (1<=k<=10)，表示测试例的个数，后面紧接着k行，每行对应一个测试例，包含一个正整数x。

Output

每个测试例对应一行输出，输出x的素数乘积表示式，式中的素数从小到大排列，两个素数之间用“*”表示乘法。

Sample Input

2
11
9828

 

Sample Output

11
2*2*3*3*3*7*13
#include <cstdio>	
using namespace std;
int main()
{
	int a[70000];
	int k, index, n;
	int i;
	
	scanf("%d", &k );
	while( k-- ){ 
		scanf("%d", &n );
		index = 0;
		for( i=2; i<=n; i++ ){
		/*输入的n不断被拆分为它的因子之积，而且都是素因子，这与用速筛的方法
		判断素数是一样的。例如n的因子有8，首先不停地除2，那么会被写成2*2*2，
		这样4和8都不会再出现了，同理9会被写成3*3，这样就不会出现合数 */
			while( n%i == 0 ){
				a[index++] = i;
				n = n/i;
			}
		}
		printf("%d", a[0] );
		for( i=1; i<index; i++ ){
			printf("*%d", a[i] );
		}
		printf("\n");
	} 
	
	return 0;	
}