Load Testing (Small)

Next year's programming contest site expects $P$ participants at once, and you have to confirm in advance that the site survives that load.

During last year's contest you learned that the site handles at least $L$ people at a time without any errors. You also know that the site cannot handle $P$ people yet.

To decide how many more machines you need, you want to know within a factor of $C$ how many people the site supports. That means finding an integer $a$ for which you know the site supports $a$ people and you know the site does not support $a \times C$ people.

You can run a series of load tests. One load test picks an integer $X$ of your choice and tells you whether the site supports at least $X$ people. You may choose each test after seeing the results of the previous ones.

With an optimal strategy, how many load tests do you need in the worst case?

The first line contains the number of test cases $T$.

Each of the next $T$ lines contains the integers $L$, $P$ and $C$ in that order, separated by spaces.

Limits

• $1 \le T \le 1000$
• $1 \le L < P \le 1000$
• $2 \le C \le 10$
• $L$, $P$ and $C$ are all integers.

For each test case, print one line in the form Case #x: y. Here $x$ is the case number starting from 1, and $y$ is the number of load tests you need in the worst case before you know within a factor of $C$ how many people the site supports.

For $L = 19$, $P = 57$, $C = 3$ you already know that the site supports 19 people and does not support 57. Those two values are exactly a factor of 3 apart, so no test is needed.

For $L = 24$, $P = 97$, $C = 2$ you could test 48 first. If the site supports 48 people, more testing is needed because $48 \times 2 < 97$. You could test 49 instead. If the site does not support 49 people, more testing is needed because $24 \times 2 < 49$. Either way the worst case takes two tests.