Problems
Prime Factors
Prime Factors
Given a natural number N. Lay it on the prime factors.
Input data
The first line of input contains the number of T (1 ≤ T ≤ 10000) of natural numbers to be decomposed into prime factors. Each of the next T lines contains a single integer N (2 ≤ N ≤ 10 000 000).
Output data
For each number N of the input data in a single line through the gap carry him the prime factors in the format shown in the examples.
Do not put extra spaces, otherwise you will get a "Wrong Answer". For example, if N is 4, you need to remove "2 * 2" (no space after the second two).
Examples
Input example #1
6 2 4 6 13 81 100
Output example #1
2 2 * 2 2 * 3 13 3 * 3 * 3 * 3 2 * 2 * 5 * 5