Given a natural number \textbf{N}. Lay it on the prime factors. \InputFile The first line of input contains the number of \textbf{T} (\textbf{1} ≤ \textbf{T} ≤ \textbf{10000}) of natural numbers to be decomposed into prime factors. Each of the next \textbf{T} lines contains a single integer \textbf{N }(\textbf{2} ≤ \textbf{N} ≤ \textbf{10 000 000}). \OutputFile For each number \textbf{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 "\textbf{Wrong Answer}". For example, if \textbf{N} is \textbf{4}, you need to remove "\textbf{2 * 2}" (no space after the second two).