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

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

Условие

Роман коллекционирует числа, кажущиеся ему интересными. Например, сейчас он считает интересными положительные числа, запись которых в системе счисления с основанием k заканчивается нечетным числом нулей. Например, при k=2 такими числами являются 2₁₀=10₂, 24₁₀=11000₂.

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

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

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

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

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

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

Ограничения

1 ≤ n ≤ 10¹⁵

2 ≤ k ≤ 10

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

№	Входной файл (numbers.in)	Выходной файл (numbers.out)
1	1 2 скопировать	2 скопировать
2	10 10 скопировать	110 скопировать

---