you have T numbers and for each number N you want to print all of it's prime factors. Expected complexity : 0(logn) for each query. You can do linear time preprocessing.
Input Format
The first line contains integer T (number of queries). Next t lines contain integer n.
Output Format
for each number n print all of it's prime factors.
Constraints
1<= T <= 10000 1<= n <= 100000
Example
Input
5 10 15 23 93 39
Output
2 5 3 5 23 3 31 3 13