問題文

非負整数 $x, y$ と $2$ 以上の整数 $a$ が与えられます。

はじめ黒板には $x$ が書かれています。これに対しあなたは以下のいずれかの操作を何回でも行うことができます（一度も行わなくても良いです）。

• 黒板に書かれた整数 $z$ を $z + 1$ に書き換える。
• 黒板に書かれた整数 $z$ を $z - 1$ に書き換える。ただし $z = 0$ のときこの操作を行うことはできない。
• 黒板に書かれた整数 $z$ を $z \times a$ に書き換える。
• 黒板に書かれた整数 $z$ を $\lfloor \frac{z}{a} \rfloor$ に書き換える。

黒板に書かれた整数を $y$ にするために必要な操作回数の最小値を求めてください。

$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力

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

ただし test$_i$ は $i$ 番目のテストケースを表し、以下の形式で与えられる。

$x \ y \ a$

• 入力される値はすべて整数
• $1 \le T \le 10^4$
• $0 \le x, y \le 10^{18}$
• $2 \le a \le 10^{18}$

出力

$T$ 行出力してください。$i$ 行目には $i$ 個目のテストケースの答えを出力してください。

サンプル

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

2
4
41
0