CF2075A To Zero

给定两个整数 $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. 从 $39$ 中减去 $5$（奇校验），得到 $34$； 2. 执行五次减去 $6$（偶校验）的操作，得到 $4$； 3. 最后减去 $4$，得到 $0$。 第二个示例中，可以： 1. 先减去 $3$（奇校验）一次； 2. 再执行三次减去 $2$（偶校验）的操作。 第三个示例中，可以直接执行三次减去 $2$（偶校验）的操作。 翻译由 DeepSeek R1 完成