题目描述

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

输入输出样例 #1

输入 #1

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

输出 #1

7
4
3
499983901
1
2
499999999
500000000

说明/提示

第一个示例中，可以按以下步骤操作：

1. 从 $39$ 中减去 $5$（奇校验），得到 $34$；
2. 执行五次减去 $6$（偶校验）的操作，得到 $4$；
3. 最后减去 $4$，得到 $0$。

第二个示例中，可以：

1. 先减去 $3$（奇校验）一次；
2. 再执行三次减去 $2$（偶校验）的操作。

第三个示例中，可以直接执行三次减去 $2$（偶校验）的操作。