Даны два целых числа $$$n$$$ и $$$k$$$; $$$k$$$ — нечетное число не меньше $$$3$$$. Ваша задача — превратить $$$n$$$ в $$$0$$$.
Для этого вы можете совершать следующую операцию любое количество раз: выбрать число $$$x$$$ от $$$1$$$ до $$$k$$$ и вычесть его из $$$n$$$. Однако если текущее значение $$$n$$$ четное (делится на $$$2$$$), то и $$$x$$$ надо выбирать четное, а если текущее значение $$$n$$$ нечетное (не делится на $$$2$$$), то и $$$x$$$ должно быть нечетным.
В разных операциях можно выбирать как разные $$$x$$$, так и одинаковые. То есть нет никаких ограничений на использование одного и того же значение $$$x$$$ несколько раз.
Посчитайте минимальное количество операций, за которое можно превратить $$$n$$$ в $$$0$$$.
В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 10000$$$) — количество наборов входных данных.
Каждый набор входных данных состоит из одной строки, содержащей два целых числа $$$n$$$ и $$$k$$$ ($$$3 \le k \le n \le 10^9$$$, $$$k$$$ нечетное).
Для каждого набора входных данных выведите одно целое число — минимальное количество операций, за которое $$$n$$$ можно превратить в $$$0$$$.
839 79 36 3999967802 35 56 5999999999 31000000000 3
7 4 3 499983901 1 2 499999999 500000000
В первом примере из условия можно сначала вычесть $$$5$$$ из числа $$$39$$$ и получить $$$34$$$. Затем пять раз вычесть $$$6$$$ и получить $$$4$$$. Затем вычесть $$$4$$$ и получить $$$0$$$.
Во втором примере можно один раз вычесть $$$3$$$, а потом три раза вычесть $$$2$$$.
В третьем примере можно три раза вычесть $$$2$$$.
