从A到B

我们来做一个数字游戏，通过一系列操作把一个数字 A 变成另一个数字 B。设当前数字是 X，规定每次操作可以从以下 3 种里面选一种进行：

- X = X + 1

- X = X - 1

- X = X × N

你的任务就是求出从 A 变成 B 至少需要多少步。

时间限制：1000

内存限制：65536

输入

每组输入包含多个测试用例。先给出一个整数 K（≤ 10），为测试用例的个数。随后 K 行，每行给出一个测试用例的三个整数：A、B、N，其中 -10⁵ ≤ A, B ≤ 10⁵，1 < N < 10。同行数字间以空格分隔。

输出

对每个测试用例，在一行中输出从 A 变成 B 至少需要多少步。

样例输入

3
3 11 2
-5 -12 3
-2 1000 7

样例输出

3
2
13

提示

样例解释： 第 1 组：(3 × 2 × 2)-1=11 第 2 组：(-5+1) × 3 = -12 第 3 组：(((-2+1+1+1+1+1)×7-1)×7+1+1+1)×7-1 = 1000