Разные системы счисления

Маленькому Арсению на кружке по системам счисления задали следующую задачу: перевести число X в системе счисления s1 в систему счисления s2. Недолго думая, он позвал на помощь своего лучшего друга Добрыню, который славился тем, что замечательно умел считать до 10 на пальцах. После нескольких бессонных ночей ребята общими усилиями справились с задачей.

 

Однако, на следующем занятии Арсению задали похожую задачу, где X, к сожалению, превышало 10. Тогда ребята решили обратиться в Летнюю Компьютерную Школу с просьбой написать универсальную программу, которая решает задачу для любых X, s1 и s2. Ваша цель – выполнить просьбу Арсения и Добрыни.

 

Во входных данных вашей программе дается 3 числа: исходное число X, основания систем счисления s1 и s2 (\(2  <=  s1,\ s2  <=  10\)). Число X в десятичной системе счисления не превышает \(2 \cdot 10^9\).

 

В выходных данных должно находиться одно число, равное числу X в системе счисления s2, или -1, если входные данные некорректны.

 

 

Примеры

№	Входные данные	Выходные данные
1	101 2 10	5
2	200 2 10	-1

 

Пусть x – целое положительное число, а k – натуральное число от 1 до 10. Пусть s(x, k) равно сумме цифр числа x, представленного в системе счисления по основанию k.

 

Задано n чисел a1, a2, ..., an. Необходимо вычислить последовательность bi по формуле \(b_i = s(a_i, k_1) \cdot s(a_i, k_2)\). После этого отсортировать последовательность bi по неубыванию.

 

Первая строка содержит три целых числа: n, k1, k2 (\(1 <= n <= 1000\), \(2 <= k_1, k_2 <= 10\)). Вторая строка содержит n целых чисел: ai (\(1 <= a_i <= 10^9\)).

 

В ответе выведите n чисел – bi в требуемом порядке.
 

 

Примеры

№	Входные данные	Выходные данные
1	9 10 10 1 2 3 4 5 6 7 9 8	1 4 9 16 25 36 49 64 81
2	10 2 2 1 2 4 8 16 32 64 128 256 512	1 1 1 1 1 1 1 1 1 1

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

 

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

 

Первая строка содержит в первой строке целое число n (\(1 <= n <= 100\)). Далее следует n строк, каждая строка содержит целое число от 1 до 999999999.

 

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

 

Пример

№	Входные данные	Выходные данные
1	2 2 65535	3 2 16 FFFF

Задано натуральное число n. Необходимо перевести его в k-ичную систему счисления и найти разность между произведением и суммой его цифр в этой системе счисления.

 

Например, пусть \(n = 239\), \(k = 8\). Тогда представление числа n в восьмеричной системе счисления — \(357\), а ответ на задачу равен \(3 \cdot 5 \cdot 7 ? (3 + 5 + 7) = 90\).
 

 

Строка содержит два натуральных числа: n и k (\(1 <= n <= 10^9\), \(2 <= k <= 10\)). Оба этих числа заданы в десятичной системе счисления.

 

Выведите ответ на задачу (в десятичной системе счисления).
 

 

Примеры

№	Входные данные	Выходные данные
1	239 8	90
2	1000000000 7	-34

Несмотря на кризис, компания Soft-Soft работает успешно. Директор компании принял решение выплатить сотрудникам премии. На следующий день был обнародован список счастливчиков. Чтобы не разглашать размер выплат, в списке напротив фамилий красовались странные цифры и даже буквы. Сотрудники быстро догадались, что размер премий записан в различных системах счисления. Но где и какая система счисления используется, сообразила только секретарша Танечка, которая вспомнила, что директор просил ее принести информацию о возрасте сотрудников. Она поняла, что директор отбрасывал десятки из числа, указывающего возраст, а к оставшимся единицам добавлял число 2. Полученное значение служило основанием для представления начисленной премии.

 

Помогите любопытной Танечке узнать размер премий в десятичной системе счисления. Известно, что размер премий не превышает 100000 рублей в десятичной системе счисления.

 

В первой строке  записаны два целых числа N и K – возраст и размер премии, разделенные пробелом. Возраст не превышает 100, размер премии указан в некоторой системе счисления (запись числа не содержит незначащих нулей, использует арабские цифры и заглавные английские буквы).

 

Выведите одно число – размер премии в десятичной системе счисления.
 

 

Примеры

№	Входные данные	Выходные данные
1	28 2800	2800
2	30 101	5