Ash meets an army of enemy Pokémon which he will beat by using a battle formation that are prime factors of the enemy's size

He needs your help in prime factorising the enemy's size, because how else will he defeat them?

Given an integer n (<= 10^6) your task is to prime factorize it.

Input:

The first line of the input contains t (<= 10^6) – that is the number of testcases, followed by t integers, each in a new line.

Output:

You need to output all prime factors of each number in a new line. Further, these need to be sorted.

Constraints:
1 < n <= 10^6
0 < t <= 10^6