给你两个整数 $$$n$$$ 和 $$$k$$$; $$$k$$$ 是不小于 $$$3$$$ 的奇数。你的任务是将 $$$n$$$ 变成 $$$0$$$。
为此,您可以多次执行以下操作:从 $$$1$$$ 到 $$$k$$$ 中选择一个数字 $$$x$$$,然后从 $$$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
注意
在语句的第一个示例中,您可以先从 $$$39$$$ 中减去 $$$5$$$ 得到 $$$34$$$。然后减去 $$$6$$$ 五次得到 $$$4$$$。最后减去$$$4$$$得到$$$0$$$。
在第二个示例中,您可以减去 $$$3$$$ 一次,然后减去 $$$2$$$ 三次。
在第三个示例中,您可以减去 $$$2$$$ 三次。