Занятие 5 (подготовка к олимпиаде)

Как, Вы не можете запомнить 6 или 7-значный номер телефона, появившийся на секунду на экране телевизора?! С помощью специальной методики, описываемой далее, Вы превратитесь в ходячий телефонный справочник!

Очевидно, что число 402 запомнить легче, чем число 110010010, а число 337377 запомнить легче, чем число 957472. Значит, нужно чтобы запоминаемое число, с одной стороны, содержало как можно меньше цифр, а с другой стороны, желательно, чтобы в числе было как можно больше повторяющихся цифр. В качестве критерия сложности запоминания примем сумму количества цифр в числе и количества различных цифр в числе. Запоминаемое число можно записать в другой системе исчисления, возможно, тогда его окажется легче запомнить. Например, число 65535 в шестнадцатеричной системе исчисления выглядит как FFFF. Таким образом, нужно подобрать основание системы исчисления для минимизации критерия сложности. Основание системы исчисления нужно выбирать в диапазоне от 2 до 36, тогда для представления числа можно использовать цифры 0-9 и латинские буквы A-Z.

Во входном файле в первой строке содержится целое число `n` (`1\ ≤\ n\ ≤\ 1000`). Далее следует `n` строк, каждая строка содержит целое число от 1 до 999999999.

В выходной файл для каждого числа вывести на отдельной строке основание системы исчисления (от 2 до 36), минимизирующее критерий сложности запоминания, и число в выбранной системе исчисления, разделенные одним пробелом. Если несколько оснований дают одинаковое значение критерия, то выбрать наименьшее среди них.

2
2
65535

3 2
16 FFFF