Problem
How can you not remember a 6 or 7 digit phone number that appears for a second on the TV screen?! With the help of a special technique described below, you will become a walking telephone directory!
Obviously, the number 402 is easier to remember than the number 110010010, and the number 337377 is easier to remember than the number 957472. So, on the one hand, it is necessary that the number to be remembered contains as few digits as possible, and on the other hand, it is desirable that the number had as many repeating digits as possible. As a criterion for the complexity of memorization, we will take the sum of the number of digits in the number and the number of different digits in the number. The memorized number can be written in a different number system, perhaps then it will be easier to remember. For example, the number 65535 looks like FFFF in hexadecimal.
Write a program for selecting the base of the number system to minimize the complexity criterion. The base of the number system must be chosen in the range from 2 to 36, then the numbers 0-9 and the English letters A-Z can be used to represent the number.
Input
The first line contains the integer n (\(1 <= n <= 100\)) in the first line. This is followed by n lines, each line containing an integer from 1 to 999999999.
Output
Response must contain
n lines. For each of the
n given numbers, the line contains: the base of the number system (from 2 to 36), which minimizes the memory difficulty criterion, and the number in the chosen number system, separated by one space. If several bases give the same value of the criterion, then choose the smallest among them.
Example
| # |
Input |
Output |
| 1 |
2
2
65535
|
3 2
16FFFF
|