CF2236C.Omsk Programmers

An annual programmers fair is taking place on the main square of Omsk. You, as the main programmer of Omsk, decided to take part in this wonderful event and went there. At the entrance, a guard decided to check your skills and gave you a problem:

You are given three integers $a$, $b$, $x$. You want to make $a$ and $b$ equal. In order to do so, you can apply the following operations:

1. Choose one of the integers $a$ or $b$ and add $1$ to it.
2. Choose one of the integers $a$ or $b$ and divide it by $x$ with rounding down.

You need to find the minimum number of operations after which $a$ becomes equal to $b$. Can you prove your skills, or will you have to go back home?

一年一度的程序员博览会正在鄂木斯克主广场举行。作为鄂木斯克首席程序员，你决定参加这场盛大的活动并前往现场。在入口处，一名守卫决定检验你的编程能力，并向你提出以下问题：

给定三个整数 $a$、$b$ 和 $x$。你的目标是使 $a$ 与 $b$ 相等。为此，你可以执行以下两种操作之一：

1. 选择 $a$ 或 $b$ 中的一个整数，并将其加 $1$；
2. 选择 $a$ 或 $b$ 中的一个整数，并将其除以 $x$（向下取整）。

你需要求出使 $a$ 等于 $b$ 所需的最少操作次数。你能否证明自己的实力，还是只能打道回府？

The first line contains a single integer $t$ $(1 \le t \le 10^4)$ — the number of test cases.

Then $t$ test cases follow.

Each test case consists of a single line containing three integers $a$, $b$, $x$ ($1 \le a, b \le 10^9$, $2 \le x \le 10^9$).

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

接下来是 $t$ 个测试用例。

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

For each test case, output a single integer — the minimum number of operations required to make $a$ and $b$ equal.

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

null