Prime Sort

Problem Description

During your lunch breaks, Rar the Cat was thinking about how to set problems to test you guys on primes. He then decided to combine sorting and prime together.

Each number above 1 can be uniquely prime factorized. Eg: 12 = 2 * 2 * 3, 15 = 3 * 5. As such, given a list of N numbers, where each number is greater than 1 and not more than 1000000, your task is to sort it based on their prime factorization.

Refer to Sample Testcases for further elaboration and inference.

Input

The first line of input consist of 1 integer, N. N lines will follow with one integer each, these N lines are the list of N numbers you have to sort based on their prime factorization.

Output

Output the sorted list of N numbers, 1 number per line.

Subtasks

Subtask 1 (7%): N = 10.

Subtask 2 (24%): N = 3000.

Subtask 3 (26%): N = 50000.

Subtask 4 (43%): N = 1000000. (Memory Limit Reduced)

Subtask 5 (0%): Sample

Sample Testcase 1

Input:

5
2 3 4 5 6

Output:

2
4
6
3
5

Explanation:

2 = 2
3 = 3
4 = 2 * 2
5 = 5
6 = 2 * 3

The numbers are differeniated by the first (lowest) prime factor first, and then followed by the second prime factor if both numbers have second prime factors. If not, the smaller number should be sorted first.