← 返回题目列表

Codeforces · 2236/C

C. 鄂木斯克程序员

中文机器翻译题面 查看原题

一年一度的程序员博览会正在鄂木斯克的主广场举行。您作为鄂木斯克的主要程序员,决定参加这个精彩的活动并前往那里。在入口处,一名警卫决定检查你的技能,并给你出了一个问题:

给你三个整数 $$$a$$$、$$$b$$$、$$$x$$$。您想让 $$$a$$$ 和 $$$b$$$ 相等。为此,您可以应用以下操作:

  1. 选择整数 $$$a$$$ 或 $$$b$$$ 之一,并将 $$$1$$$ 添加到其中。
  2. 选择整数 $$$a$$$ 或 $$$b$$$ 之一,然后除以 $$$x$$$ 并向下舍入。

您需要找到 $$$a$$$ 等于 $$$b$$$ 后的最小操作数。你能证明你的技能吗?还是你必须回家?

输入

第一行包含一个整数 $$$t$$$ $$$(1 \le t \le 10^4)$$$ — 测试用例的数量。

然后是 $$$t$$$ 测试用例。

每个测试用例由一行组成,其中包含三个整数 $$$a$$$、$$$b$$$、$$$x$$$ ($$$1 \le a, b \le 10^9$$$, $$$2 \le x \le 10^9$$$)。

输出

对于每个测试用例,输出一个整数 - 使 $$$a$$$ 和 $$$b$$$ 相等所需的最少操作数。

示例

输入
复制

7
1 2 3
2 3 2
7 3 10
17 3 3
10 10 2
4 7 2
1 6 2

输出
复制

1
1
2
3
0
2
2