Description

Little C is a hard worker who trains every day.

Little C starts with an initial ability value $a$ and aims to reach a target ability value $b$. Both $a$ and $b$ are non-negative integers, and it is guaranteed that $a < b$. There is a positive integer $k$. Each day, Little C can choose one of the following two training methods:

• Normal training: After training, Little C's ability value becomes $a + k$.
• Train harder: After training, Little C's ability value becomes $a \times k$.

Little C wants to know: what is the minimum number of days required to make his ability value greater than or equal to $b$?

Input Format

Only one line containing two non-negative integers $a$, $b$ and one positive integer $k$, representing the initial ability value, the target ability value, and the parameter for ability growth, respectively.

Output Format

Output one line containing a positive integer, which is the answer.

2 4 2

1

1 100 3

4

0 5 2

3

1 3 8

1

Hint

Explanation #1

Choose normal training. After training, the ability value becomes $2 + 2 = 4$, achieving the goal in one day.

Explanation #2

The training plan is as follows:

• On the first day, choose normal training. After training, the ability value becomes $1 + 3 = 4$.
• On the second day, choose train harder. After training, the ability value becomes $4 \times 3 = 12$.
• On the third day, choose train harder. After training, the ability value becomes $12 \times 3 = 36$.
• On the fourth day, choose train harder. After training, the ability value becomes $36 \times 3 = 108$.

The goal is achieved in four days.

Explanation #3

The training plan is as follows:

• On the first day, choose normal training. After training, the ability value becomes $0 + 2 = 2$.
• On the second day, choose normal training. After training, the ability value becomes $2 + 2 = 4$.
• On the third day, choose normal training. After training, the ability value becomes $4 + 2 = 6$.

The goal is achieved in three days.

Data Range

For $30\%$ of the data, $2 \le a < b \le 10^3$, $k \ge 2$.

For another $20\%$ of the data, $k = 1$.

For all data, $0 \le a < b \le 10^6$, $1 \le k \le 10^6$.

Translated by DeepSeek V3.1