一年一度的程序员博览会正在鄂木斯克的主广场举行。您作为鄂木斯克的主要程序员,决定参加这个精彩的活动并前往那里。在入口处,一名警卫决定检查你的技能,并给你出了一个问题:
给你三个整数 $$$a$$$、$$$b$$$、$$$x$$$。您想让 $$$a$$$ 和 $$$b$$$ 相等。为此,您可以应用以下操作:
- 选择整数 $$$a$$$ 或 $$$b$$$ 之一,并将 $$$1$$$ 添加到其中。
- 选择整数 $$$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$$$ 相等所需的最少操作数。
示例
输入复制
71 2 32 3 27 3 1017 3 310 10 24 7 21 6 2
输出复制
1123022