Natural numbers from 1 to n are written in a row and a natural number k is given.
One or more steps are taken to remove the numbers in this row. On
In the next step, the remaining numbers are looked up in ascending order, and every kth number is removed. If after the next step there are less than k numbers left, then the process of deleting numbers ends.
You need to determine at which step the number n will be removed, or find out that it will not be removed until the process ends.
For example, let n = 13, k = 2.
- The first step will remove the numbers 2, 4, 6, 8, 10 and 12, leaving the numbers 1, 3, 5, 7, 9, 11 and 13.
- In the second step, the numbers 3, 7 and 11 will be removed, leaving the numbers 1, 5, 9 and 13.
- In the third step, the numbers 5 and 13 will be removed, leaving the numbers 1 and 9.
- In the fourth step, the number 9 will be removed, leaving the number 1. Since one number remains, the process ends.
Thus, the number 13 will be removed in the third step.
You need to write a program that, given the numbers n and k, determines at what step the number n will be removed.
Input data format
The first line of the input contains an integer n (3 ≤ n ≤ 1018).
The second line of the input contains an integer k (2 ≤ k ≤ 100, k < n).
Output format
Required to output a single integer — the number of the step at which the number n will be removed, or the number 0 if the number n is not removed.