# Sorting by the number of divisors P64854

Statement

thehtml

Given n natural numbers, sort them. First, by its number of divisors (the larger the better); in case of a tie, by its number of digits (the larger the better); and in case of another tie, by its value (the smaller the better).

Input

Input consists of several cases, each one with n followed by n numbers between 1 and 107. You can assume 1 ≤ n ≤ 104.

Output

For every case, print n lines with every number and its number of divisors, sorted as it is explained above. Print a line with 10 dashes at the end of every case.

Hint

Rememeber that, if the factorization of a number is p1q1pmqm, then its number of divisors is (q1 + 1) ⋯ (qm + 1). For instance, for 12 = 22 · 31 there are (2 + 1) · (1 + 1) = 6 divisors.

Public test cases
• Input

```9  12 1 5 1000 10 8 9 34549 10007
4  10000000 9999999 9999998 9999997
3  23 23 23
```

Output

```1000 16
12 6
10 4
8 4
9 3
10007 2
34549 2
5 2
1 1
----------
10000000 64
9999999 12
9999997 4
9999998 4
----------
23 2
23 2
23 2
----------
```
• Information
Author