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.