题目描述

一年一度的程序员博览会在鄂木斯克的主广场举行。作为鄂木斯克的首席程序员，你决定参加这场精彩的活动并前往现场。入口处，一名守卫决定测试你的技能，并给了你一个问题：

给定三个整数 (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