Description

现在你已经赢得了 Code Jam 并被 Google 雇佣为软件工程师，你被分配到他们极受欢迎的编程竞赛网站工作。

Google 预计明年会有很多参赛者（$P$）参加 Code Jam，他们希望确保网站能够同时支持这么多人。在 2010 年的 Code Jam 期间，你了解到该网站至少可以同时支持 $L$ 个人而不会出错，但你也知道目前网站还无法支持 $P$ 个人。

为了确定还需要增加多少台机器，你希望知道网站最多能支持多少人，误差在 $C$ 倍以内。也就是说，存在一个整数 $a$，你知道网站可以支持 $a$ 个人，但不能支持 $a \times C$ 个人。

你可以进行一系列的“负载测试”，每次测试可以确定网站是否能支持至少 $X$ 个人（$X$ 是你选择的整数）。如果你采用最优策略，根据前面测试的结果选择后续的测试，那么在最坏情况下，你需要进行多少次负载测试，才能确定网站最多能支持多少人，误差在 $C$ 倍以内？

Input Format

输入的第一行包含测试用例的数量 $T$。接下来的 $T$ 行，每行包含用空格分隔的三个整数 $L$、$P$ 和 $C$。

Output Format

对于每个测试用例，输出一行，格式为 "Case #$x$: $y$"，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是在最坏情况下你需要进行的负载测试次数，才能确定网站最多能支持多少人，误差在 $C$ 倍以内。

4
50 700 2
19 57 3
1 1000 2
24 97 2

Case #1: 2
Case #2: 0
Case #3: 4
Case #4: 2

Hint

样例解释

在第 2 个测试用例中，我们已经知道网站可以支持 $19$ 到 $57$ 个人。由于这两个数相差 $3$ 倍，因此我们不需要进行任何测试。

在第 4 个测试用例中，我们可以测试 $48$；但如果网站能支持 $48$ 个人，还需要继续测试，因为 $48 \times 2 < 97$。我们可以测试 $49$；但如果网站不能支持 $49$ 个人，还需要继续测试，因为 $24 \times 2 < 49$。所以我们需要进行两次测试。

数据范围

• $1 \leqslant T \leqslant 1000$。
• $2 \leqslant C \leqslant 10$。
• $L$、$P$ 和 $C$ 均为整数。

小数据集（14 分，测试集 1 - 可见）

• $1 \leqslant L < P \leqslant 10^3$。

大数据集（22 分，测试集 2 - 隐藏）

• $1 \leqslant L < P \leqslant 10^9$。

由 ChatGPT 4.1 翻译