# Prime Factors Using Sieve

medium

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.

## Constraints

1<= T <= 10000 1<= n <= 100000

## Format

### Input

The first line contains integer T (number of queries). Next t lines contain integer n.

### Output

for each number n print all of it's prime factors.

## Example

Sample Input

5
10
15
23
93
39

### Sample Output

2 5
3 5
23
3 31
3 13