C. Omsk Programmers
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

An annual programmers fair is taking place on the main square of Omsk. You, as the main programmer of Omsk, decided to take part in this wonderful event and went there. At the entrance, a guard decided to check your skills and gave you a problem:

You are given three integers $$$a$$$, $$$b$$$, $$$x$$$. You want to make $$$a$$$ and $$$b$$$ equal. In order to do so, you can apply the following operations:

  1. Choose one of the integers $$$a$$$ or $$$b$$$ and add $$$1$$$ to it.
  2. Choose one of the integers $$$a$$$ or $$$b$$$ and divide it by $$$x$$$ with rounding down.

You need to find the minimum number of operations after which $$$a$$$ becomes equal to $$$b$$$. Can you prove your skills, or will you have to go back home?

Input

The first line contains a single integer $$$t$$$ $$$(1 \le t \le 10^4)$$$ — the number of test cases.

Then $$$t$$$ test cases follow.

Each test case consists of a single line containing three integers $$$a$$$, $$$b$$$, $$$x$$$ ($$$1 \le a, b \le 10^9$$$, $$$2 \le x \le 10^9$$$).

Output

For each test case, output a single integer — the minimum number of operations required to make $$$a$$$ and $$$b$$$ equal.

Example
Input
7
1 2 3
2 3 2
7 3 10
17 3 3
10 10 2
4 7 2
1 6 2
Output
1
1
2
3
0
2
2