Задача E. Тимофей вычёркивает числа

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

В Научно-исследовательском институте, где работает Тимофей, продолжается успешное исследование ряда натуральных чисел. Каждый день его коллеги открывают всё новые и новые свойства этой последовательности, и Тимофей старается от них не отставать. Сегодня утром, как обычно, научные работники составили ряд натуральных чисел, а после обеда, в соответствии с распоряжением начальника отдела, последовательно выполняли следующую операцию: удалить из натурального ряда все числа, позиции которых делятся нацело на k.

На какой по счёту операции было удалено число n?

Формат входных данных

Две строки входного файла содержат натуральные числа n и k.

textbfОбратитевнимание, что при заданных ограничениях для хранения значений переменных необходимо использовать 64-битный тип данных, например textbflong textbflong в textbfC +  + , textbfint64 в textbfFree textbfPascal, textbflong в textbfJava.

Формат выходных данных

Выведите одно натуральное число — ответ на вопрос задачи.

Ограничения

1 ≤ k ≤ n ≤ 1015

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при n ≤ 105, получат не менее 20 баллов.

Пояснение к примеру

В примере дано n = 20 и k = 3. Из натурального ряда за одну операцию будут вычеркнуты все числа, позиции которых делятся на 3. Определим, на какой операции будет вычеркнуто число 20. Смотри рисунок.

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

Стандартный вход Стандартный выход
1
20
3
7

0.078s 0.013s 17