eolymp
bolt
Try our new interface for solving problems
Problems

Identification Codes

Identification Codes

Time limit 1 second
Memory limit 64 MiB

MI6 uses a Spy Identification Code (SIC) to identify their spies. For example, J. B.^2 has a SIC of 7. The SICs have been assigned to the spies in such a way that MI6 can easily refer to any group of spies by using a status code that is the product of all SICs of the spies in the group. More precisely, the SICs are chosen in such a way that each status code ≥ 2 refers to a unique group of spies, and for each group of spies there is a unique status code referring to it.

Write a program that, given a status code, returns the SICs of the spies that belong to the group corresponding to that status code.

__________________

^2For security reasons his full name is kept secret, but rumour has it that he is one of the jury members.

Input data

On the first line one positive number: the number of test cases, at most 100. After that per test case:

  • one line with an integer c (2c10^9): the status code.

Output data

Per test case:

  • one line with a space-separated list of SICs for the status code, in increasing order.

Examples

Input example #1
5
7
12
64
72
1337
Output example #1
7
3 4
4 16
2 4 9
7 191
Source 2013 Benelux Algorithm Programming Contest (BAPC), Preliminaries, September 28, Problem I