题目描述

给定两个整数 $n$ 和 $k$，其中 $k$ 是不小于 $3$ 的奇数。你的任务是将 $n$ 变为 $0$。

为此，你可以执行以下操作任意次数：从 $1$ 到 $k$ 中选择一个数 $x$，并将其从 $n$ 中减去。但需注意：

• 若当前 $n$ 是偶数，则 $x$ 也必须是偶数；
• 若当前 $n$ 是奇数，则 $x$ 也必须是奇数。

在不同操作中， $x$ 的值没有任何限制。

请计算将 $n$ 变为 $0$ 所需的最少操作次数。

输入格式

本题有多组数据

第一行输入一个整数 $t$ 代表测试数据组数，接下来每一组数据：

• 输入两个空格隔开的整数分别代表 $n,k$，其中保证 $k$ 是奇数。

输出格式

输出一共输出 $t$ 行，每行一个整数代表答案。

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

提示

样例 1 解释

第一组数据中，可以按以下步骤操作：

• 从 $39$ 中减去 $5$，得到 $34$。
• 执行五次减去 $6$ 的操作，得到 $4$。
• 最后减去 $4$，得到 $0$。

第二组数据中，可以：

• 先减去 $3$ 一次。
• 再执行三次减去 $2$ 的操作。

第三组数据中，可以直接执行三次减去 $2$ 的操作。

数据范围

对于 $100\%$ 的数据，$1\le t\le 10^4$，$3\leq k\leq n\leq 10^9$，保证 $k$ 是奇数。

• 子任务 $1$（$30$ 分）：$n\leq 100$。
• 子任务 $2$（$30$ 分）：保证 $n$ 是偶数。
• 子任务 $3$（$40$ 分）：没有特殊限制。