A. 归零
每次测试的时间限制：2 秒
每次测试的内存限制：512 兆字节

题目描述

给你两个整数 $n$ 和 $k$，其中 $k$ 是大于等于 $3$ 的奇数。你的目标是通过若干次操作将 $n$ 变为 $0$。

每次操作，你可以选择一个数 $x$，其中 $1 \le x \le k$，然后从当前的 $n$ 中减去 $x$。
但是，如果当前的 $n$ 是偶数（能被 $2$ 整除），那么你选择的 $x$ 必须是偶数；
如果当前的 $n$ 是奇数（不能被 $2$ 整除），那么你选择的 $x$ 必须是奇数。

不同的操作中你可以选择相同的 $x$ 值（没有限制）。

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

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10000$）—— 测试用例的数量。

每个测试用例由一行包含两个整数 $n$ 和 $k$（$3 \le k \le n \le 10^9$，$k$ 是奇数）。

输出格式

对于每个测试用例，输出一个整数 —— 所需的最小操作次数。

示例

输入

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$。
  共 $1 + 5 + 1 = 7$ 次操作。

• 第二个例子：
  减去 $3$ 一次，再减去 $2$ 三次。
  共 $1 + 3 = 4$ 次操作。

• 第三个例子：
  减去 $2$ 三次。
  共 $3$ 次操作。