Игорь очень любит 16-ричную систему счисления и считает целое положительное число в 16-ричной системе счисления интересным, если каждая цифра и буква в нём встречается не более t раз. Например, если t = 3, то числа 13a13322, aaa, abcdef0123456789 — интересные, а числа aaaa, abababab и 1000000 — нет.
Перед вами стоит задача найти k-е по счёту интересное для Игоря число в 16-ричной системе счисления. Число не должно содержать лидирующих нулей.
Выходные данные
Выведите единственное целое число в 16-ричной системе счисления, которое является k-м по счёту интересным для Игоря числом в 16-ричной системе счисления.
Примечание
Первые 20 чисел, которые является интересными, если t = 1: 1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, c, d, e, f, 10, 12, 13, 14, 15. Поэтому ответ на первый пример равен 12.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
17 1
|
12
|
|
2
|
1000000 2
|
fca2c
|