Problem D
Emergency Contest Running
Löpkass is out running in the forest again. He loves running in the forest. However, there is a programming competition starting in a couple of hours, and he needs to calculate how long it will take him to get home (so that he can stay in the fresh air as long as possible). You have to help him out.
The forest is modelled as a graph with $n$ nodes. Nodes are numbered $0, 1, ..., n-1$. Löpkass is located in node $0$, and his home is located in node $n-1$. Two nodes $v,w$ are connected if $v+1 = w$. Additionally, two nodes are connected if they are both a multiple of some integer $K$. In this problem, we do not consider $0$ to be a multiple of $K$.
Input
One line with two integers, the number of nodes $1 \leq n \leq 10^{18}$, and the number $1 \leq K \leq 10^{18}$.
Output
Print a single integer on a single line: the shortest path from node 0 to node $n-1$.
| Sample Input 1 | Sample Output 1 |
|---|---|
5 2 |
3 |
| Sample Input 2 | Sample Output 2 |
|---|---|
2 4 |
1 |
