Description

One morning, Muro found that a piece of cake he had secretly kept was eaten! He immediately guessed that one of the pigs had eaten the cake, so he rushed to the pigsty to find that pig and punish it.

There are $n$ pigs in the pigsty, numbered with integers from $1$ to $n$. Except for the pig that ate the cake, all other pigs have the same weight, and the pig that ate the cake is slightly heavier than the others (you may assume the pigs were originally $5\text{kg}$, and the one that ate the cake is $5.1\text{kg}$). Muro cannot tell by sight which pig ate the cake.

Fortunately, Muro has a balance scale. He can drive pigs onto the two sides of the scale to compare which side is heavier. However, this scale is not very large: each side can hold at most $m$ pigs, otherwise the scale will be damaged and become unusable (the pig that ate the cake will not reduce the number of pigs that can be placed on one side, i.e., whether or not a pig ate the cake, each side can still hold at most $m$ pigs).

Muro does not want to spend too much time, so he wants to know, under the condition that the scale is not damaged, at least how many weighings are needed to guarantee finding the pig that ate the cake. Please compute this number.

Input Format

One line with two positive integers $n,m$.

Output Format

One line with one positive integer, the answer.

4 5

2

13 6

3

8 2

3

114 514

5

19198 10

962

Hint

Explanation for Sample 1:

Muro first puts pig $1$ and pig $2$ onto the two sides of the scale respectively, then puts pig $3$ and pig $4$ onto the two sides respectively. In this way, he can definitely find the pig that ate the cake, and the number of weighings is $2$. Obviously, using the scale only once cannot guarantee finding the pig that ate the cake.

Explanation for Sample 3:

Each side of the scale can hold at most $2$ pigs, so at least $3$ weighings are needed to guarantee finding it.

Constraints

This problem uses bundled testdata.

• Subtask 1 ( $10\%$ ): $n,m\leq10$.
• Subtask 2 ( $25\%$ ): $n,m\leq10^6$.
• Subtask 3 ( $15\%$ ): $n\leq m$.
• Subtask 4 ( $50\%$ ): no special constraints.

For all testdata, $1\leq n,m\leq10^{15}$.

Translated by ChatGPT 5