2236C.md (1379B)
1 Source: https://codeforces.com/problemset/problem/2236/C 2 3 C. Omsk Programmers 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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: 22 23 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: 24 25 1. Choose one of the integers $a$ or $b$ and add $1$ to it. 26 2. Choose one of the integers $a$ or $b$ and divide it by $x$ with rounding down. 27 28 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? 29 30 Input 31 32 The first line contains a single integer $t$ $(1 \le t \le 10^4)$ — the number of test cases. 33 34 Then $t$ test cases follow. 35 36 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$). 37 38 Output 39 40 For each test case, output a single integer — the minimum number of operations required to make $a$ and $b$ equal. 41 42 Example 43 44 Input 45 46 ``` 47 7 48 49 1 2 3 50 51 2 3 2 52 53 7 3 10 54 55 17 3 3 56 57 10 10 2 58 59 4 7 2 60 61 1 6 2 62 ``` 63 64 Output 65 66 ``` 67 1 68 69 1 70 71 2 72 73 3 74 75 0 76 77 2 78 79 2 80 ```