题目描述

给定三个正整数 $a, b, x$。你的目标是使 $a$ 和 $b$ 变得相等。为了达到这个目的，你可以执行以下两种操作任意次（包括 $0$ 次）：

• 选择 $a$ 或 $b$ 中的某一个整数，将其加 $1$。
• 选择 $a$ 或 $b$ 中的某一个整数，将其除以 $x$ 并向下取整。

请计算，最少需要多少次操作才能使 $a$ 和 $b$ 变得相等。

输入格式

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

接下来 $t$ 行，每行包含三个整数 $a, b, x$ —— 分别表示给定的三个数。

输出格式

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

样例输入 1

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

样例输出 1

1
1
2
3
0
2
2

说明

数据范围

• 对于所有测试点，保证 $1 \le t \le 10^4$。
• 对于每个测试用例，保证 $1 \le a, b \le 10^9$ 且 $2 \le x \le 10^9$。
• 保证所有的输入数值均为整数。