Sorting by the number of divisors P64854

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 \le n \le 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^{q_1} \cdots p_m^{q_m}$, then its number of divisors is $(q_1 + 1) \cdots (q_m + 1)$. For instance, for $12 = 2^2 \cdot 3^1$ there are $(2 + 1) \cdot (1 + 1) = 6$ divisors.