Problem Statement

You are given non-negative integers $x, y$ and an integer $a$ that is at least $2$.

Initially, $x$ is written on a blackboard. You may perform any of the following operations any number of times (possibly zero).

• Replace the integer $z$ written on the blackboard with $z + 1$.
• Replace the integer $z$ written on the blackboard with $z - 1$. However, this operation cannot be performed when $z = 0$.
• Replace the integer $z$ written on the blackboard with $z \times a$.
• Replace the integer $z$ written on the blackboard with $\lfloor \frac{z}{a} \rfloor$.

Find the minimum number of operations required to make the integer written on the blackboard equal to $y$.

You are given $T$ test cases; find the answer for each of them.

Input

$T$
test$_1$
$\vdots$
test$_T$

Here, test$_i$ represents the $i$-th test case, which is given in the following format.

$x \ y \ a$

• All input values are integers.
• $1 \le T \le 10^4$
• $0 \le x, y \le 10^{18}$
• $2 \le a \le 10^{18}$

Output

Output $T$ lines. On the $i$-th line, output the answer for the $i$-th test case.

Sample

4
7 4 2
20 11 10
12093298 4893042 23
0 0 2

2
4
41
0