Интересные числа

Роман коллекционирует числа, кажущиеся ему интересными. Например, сейчас он считает интересным положительные числа, запись которых в системе счисления с основанием $k$ заканчивается нечетным числом нулей. Например, при $k=2$ такими числами являются $2\_{10}=10\_2$, $24\_{10}=11000\_{2}$.

Для того, чтобы пополнить свою коллекцию, Роман хочет найти $n$-ое в порядке возрастания такое число. Поскольку $n$ он взял достаточно большим, то вручную у него это сделать не получается. 

Помогите Роману --- напишите программу, которая найдет число, которое нужно ему для пополнения коллекции.

Первая строка входного файла содержит два целых числа ($1 \le n \le 10^{15}$, $2 \le k \le 10$).

В выходной файл выведите $n$-ое в порядке возрастания число, запись которого в системе счисления с основанием $k$ заканчивается на нечетное число нулей. Это число необходимо вывести в десятичной системе счисления.