CF2075A To Zero

You are given two integers $ n $ and $ k $ ; $ k $ is an odd number not less than $ 3 $ . Your task is to turn $ n $ into $ 0 $ . To do this, you can perform the following operation any number of times: choose a number $ x $ from $ 1 $ to $ k $ and subtract it from $ n $ . However, if the current value of $ n $ is even (divisible by $ 2 $ ), then $ x $ must also be even, and if the current value of $ n $ is odd (not divisible by $ 2 $ ), then $ x $ must be odd. In different operations, you can choose the same values of $ x $ , but you don't have to. So, there are no limitations on using the same value of $ x $ . Calculate the minimum number of operations required to turn $ n $ into $ 0 $ .

The first line contains one integer $ t $ ( $ 1 \le t \le 10000 $ ) — the number of test cases. Each test case consists of one line containing two integers $ n $ and $ k $ ( $ 3 \le k \le n \le 10^9 $ , $ k $ is odd).

For each test case, output one integer — the minimum number of operations required to turn $ n $ into $ 0 $ .

In the first example from the statement, you can first subtract $ 5 $ from $ 39 $ to get $ 34 $ . Then subtract $ 6 $ five times to get $ 4 $ . Finally, subtract $ 4 $ to get $ 0 $ . In the second example, you can subtract $ 3 $ once, and then subtract $ 2 $ three times. In the third example, you can subtract $ 2 $ three times.