既然你已经赢得了 Code Jam 并被 Google 聘为软件工程师，你被分配去维护他们广受欢迎的编程竞赛网站。

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

为了确定还需要多少台机器，你想在 C 倍的范围内确定网站能够支持的人数。这意味着存在一个整数 a，使得你知道网站可以支持 a 人，但你知道网站无法支持 a * C 人。

你可以进行一系列的负载测试，每一次测试都可以确定网站是否至少能支持 X 人，其中 X 是你选择的整数。如果你采用最优策略，即根据之前测试的结果来决定下一次运行什么测试，那么在最坏情况下你需要进行多少次负载测试？

输入格式

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

输出格式

对于每个测试用例，输出一行 "Case #x: y"，其中 x 是用例编号（从 1 开始），y 是在最坏情况下，为了在 C 倍的范围内确定网站能够支持的人数，你需要运行的负载测试次数。

数据范围

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

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

$1 \le L < P \le 10^3$。

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

$1 \le L < P \le 10^9$。

样例

输入格式 1

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

输出格式 1

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

说明

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

在用例 #4 中，我们可以测试 48；但如果网站可以支持 48 人，我们还需要进一步测试，因为 $48 \times 2 < 97$。我们也可以测试 49；但如果网站无法支持 49 人，我们同样需要进一步测试，因为 $24 \times 2 < 49$。因此，我们需要进行两次测试。