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⁷. You can assume 1 ≤ n ≤ 10⁴.

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₁^q₁ ⋯ p_m^q_m, then its number of divisors is (q₁ + 1) ⋯ (q_m + 1). For instance, for 12 = 2² · 3¹ there are (2 + 1) · (1 + 1) = 6 divisors.