鄂木斯克程序员

英文题名：C. Omsk Programmers
来源：Codeforces 2236C
比赛：Codeforces Round 1103 (Div. 3)
时间限制：1 second
空间限制：256 megabytes

题目描述

给定 $a,b,x$。每次可以选择 $a$ 或 $b$ 中的一个数，将它加 $1$，或将它变成除以 $x$ 后向下取整。求让 $a=b$ 的最少操作次数。

输入格式

第一行输入 $t$。每组一行输入 $a,b,x$。约束：$1\le a,b\le10^9$，$2\le x\le10^9$。

输出格式

每组输出最少操作次数。

样例

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