← 返回题目列表

Codeforces · 2075/A

A. 归零

中文机器翻译题面 查看原题

给你两个整数 $$$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$$$ 所需的最少操作数。

示例

输入
复制

8
39 7
9 3
6 3
999967802 3
5 5
6 5
999999999 3
1000000000 3

输出
复制

7
4
3
499983901
1
2
499999999
500000000

注意

在语句的第一个示例中,您可以先从 $$$39$$$ 中减去 $$$5$$$ 得到 $$$34$$$。然后减去 $$$6$$$ 五次得到 $$$4$$$。最后减去$$$4$$$得到$$$0$$$。

在第二个示例中,您可以减去 $$$3$$$ 一次,然后减去 $$$2$$$ 三次。

在第三个示例中,您可以减去 $$$2$$$ 三次。