Problem Description

There are $n$ students in Class 7 of Grade 3. When PE class begins, they stand in a line from left to right, preparing to count off and form groups.

The PE teacher has many bags of candy in his pocket (each bag contains many candies). He plans to hand out these bags of candy to the students while forming groups.

Specifically, during the counting process from left to right, every time $k$ students are counted, the PE teacher forms these $k$ students into a group, and gives one bag of candy to the last student among these $k$ students, who will be responsible for distributing it to the students in the group. In other words, the PE teacher will give a bag of candy to the $k, 2k, \cdots$-th students from left to right.

By coincidence, the students of Class 6 of Grade 3 heard the news that Class 7 of Grade 3 is giving out candy, so they plan to blend into the end of the line (the far right of the line), trying to get a bag of candy for free.

The students of Class 6 of Grade 3 want to know how many students they need to add to the end of the line at least.

Input Format

One line with two integers $n, k$.

Output Format

One line with one integer, representing the answer.

10 3

2

16 4

4

Hint

Explanation for Sample 1

Here, students are grouped every $3$ people. Class 6 of Grade 3 only needs to add $2$ students into the line, so they can form a group together with the last $1$ student of the original Class 7 of Grade 3.

Since these $2$ added students are at the end of the line, the last student in this group must be a student from the neighboring class, so the neighboring class can get a bag of candy for free.

Explanation for Sample 2

Here, students are grouped every $4$ people. All students in Class 7 of Grade 3 have already been grouped, so Class 6 of Grade 3 needs to add a full $4$ students into the line to form a group, in order to get a bag of candy for free.

Constraints

For $100\%$ of the testdata, $1 \leq n \leq 10 ^ {9}$, $2 \leq k \leq 10 ^ 9$.

Translated by ChatGPT 5