当前没有测试数据。

CF测试跳转：https://codeforces.com/contest/2236/problem/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$ 相等所需的最少操作次数。

Samples

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