Александр учится переводить числа из десятичной системы счисления в любую другую, однако он не знает латинских букв, поэтому любую цифру он записывает только десятичным числом, то есть вместо буквы A он запишет число 10. Таким образом, переводя число 475 из десятичной системы в шестнадцатеричную, он получил 11311 (475 = 1·162 + 13·161 + 11·160). Александр жил спокойно, пока не попробовал перевести число обратно в десятичную систему счисления.
Саша помнит, что работал с небольшими числами, поэтому просит найти минимальное десятичное число, при переводе которого в систему счисления с основанием n он получил бы число k.
Выходные данные
Выведите число x (0 ≤ x ≤ 1018) — ответ на задачу.
Примечание
В первом тесте 12 могло получится при переводе двух чисел в 13-ричную систему счисления 12 = 12·130 или 15 = 1·131 + 2·130.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
13
12
|
12
|
|
2
|
16
11311
|
475
|
|
3
|
20
999
|
3789
|
|
4
|
17
2016
|
594
|