Sorting by number of divisors

Go Medium sorting

Task «Sorting by number of divisors»

Write a program that sorts an array of integers in ascending order of the number of their positive divisors. If two numbers have the same number of divisors, they are sorted in ascending order of the numbers themselves. The input array may contain both positive and negative numbers. For negative numbers, the number of divisors is calculated in the same way as for their absolute value.

Input Format

The first line contains an integer N (1 ≤ N ≤ 1000) — the number of elements in the array. The second line contains N integers, each not exceeding 10^9 in absolute value, separated by spaces.

Output Format

Output N numbers in the order specified by the condition, separated by spaces.

Examples

Example 1

INPUT

5
12 2 20 101 3

OUTPUT

2 3 101 12 20

main.go