AT_abc465_d [ABC465D] X to Y

You are given integers $ X,Y $ , and an integer $ K $ that is at least $ 2 $ . There is a variable $ x $ , which is initially $ x=X $ . You can perform the following operation on $ x $ zero or more times: - Choose an integer $ y $ satisfying $ \displaystyle \left\lfloor \frac xK \right\rfloor=y $ or $ \displaystyle \left\lfloor \frac yK \right\rfloor=x $ , and replace the value of $ x $ with $ y $ . Here, $ \displaystyle \left\lfloor z \right\rfloor $ is defined as the greatest integer not exceeding $ z $ , for a real number $ z $ . Find the minimum number of operations required to make $ x=Y $ . Under the given constraints, it can be proved that there always exists a way to make $ x=Y $ in a finite number of operations. You are given $ T $ test cases; solve each of them.

The input is given from Standard Input in the following format: > $ T $ $ \text{case}_1 $ $ \text{case}_2 $ $ \vdots $ $ \text{case}_T $ The $ i $ -th $ (1\le i\le T) $ test case $ \text{case}_i $ is given in the following format: > $ X $ $ Y $ $ K $

Output the answers for the test cases in order, separated by newlines.

### Sample Explanation 1 Consider the first test case. By performing the following operations, $ x=Y $ can be achieved in two operations: - Choose $ y=3 $ . Since $ \displaystyle\left\lfloor\frac{x}K \right\rfloor=\left\lfloor\frac{11}3 \right\rfloor=3 $ , this choice is valid. Then, replace the value of $ x $ with $ 3 $ . - Choose $ y=9 $ . Since $ \displaystyle\left\lfloor\frac{y}K \right\rfloor=\left\lfloor\frac{9}3 \right\rfloor=3 $ , this choice is valid. Then, replace the value of $ x $ with $ 9 $ . $ x=Y $ cannot be achieved in fewer than two operations, so output $ 2 $ on the first line. ### Constraints - $ 1\le T\le 2\times 10^5 $ - $ 0\le X,Y\le 10^{18} $ - $ 2\le K\le 10^{18} $ - All input values are integers.