Задача D. Интересные числа

Автор:Жюри ВКОШП-2008   Ограничение времени:2 сек
Входной файл:numbers.in   Ограничение памяти:256 Мб
Выходной файл:numbers.out  

Условие

Роман коллекционирует числа, кажущиеся ему интересными. Например, сейчас он считает интересными положительные числа, запись которых в системе счисления с основанием k заканчивается нечетным числом нулей. Например, при k=2 такими числами являются 210=102, 2410=110002.

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

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

Формат входного файла

Первая строка входного файла содержит два целых числа.

Формат выходного файла

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

Ограничения

1 ≤ n ≤ 1015

2 ≤ k ≤ 10

Примеры тестов

Входной файл (numbers.in) Выходной файл (numbers.out)
1
1 2
2
2
10 10
110

0.038s 0.008s 15