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 10^{7}.
You can assume 1 ≤ n ≤ 10^{4}.

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
p_{1}^{q1} ⋯ p_{m}^{qm},
then its number of divisors is
(q_{1} + 1) ⋯ (q_{m} + 1).
For instance, for 12 = 2^{2} · 3^{1}
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
- Salvador Roura
- Language
- English
- Translator
- Salvador Roura
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- C++
- User solutions
- C++