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

Условие

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

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

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

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

$\textbf{Обратите внимание}$, что при заданных ограничениях для хранения значений переменных необходимо использовать $64$-битный тип данных, например $\textbf{long}$ $\textbf{long}$ в $\textbf{C++}$, $\textbf{int64}$ в $\textbf{Free}$ $\textbf{Pascal}$, $\textbf{long}$ в $\textbf{Java}$.

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

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

Ограничения

$1 \le k \le n \le 10^{15}$

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

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

Решения, верно работающие при $n \le 10^{5}$, получат не менее 20 баллов.

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

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

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

20
3

7