题目描述

塞西莉亚是一位温柔而智慧的圣女，她的日常不仅仅是祈祷和仪式，还包括解决各种谜题和挑战。

一天，塞西莉亚在教堂的图书馆中发现了一本古老的书籍，书中记载了一个有趣的数学游戏：将一个整数 $n$ 通过特定的规则减至 $0$。

这个游戏的规则是这样的：你可以从 $1$ 到 $k$ 中选择一个数 $x$，并将其从 $n$ 中减去。但是，选择的 $x$ 必须与当前 $n$ 的奇偶性相同——如果 $n$ 是偶数，$x$ 也必须是偶数；如果 $n$ 是奇数，$x$ 也必须是奇数。塞西莉亚被这个游戏深深吸引，她决定挑战自己，找出将 $n$ 变为 $0$ 所需的最少操作次数。

塞西莉亚需要你的帮助，计算将 $n$ 变为 $0$ 所需的最少操作次数。你可以执行以下操作任意次数：从 $1$ 到 $k$ 中选择一个数 $x$，并将其从 $n$ 中减去。但需注意，若当前 $n$ 是偶数（能被 $2$ 整除），则 $x$ 也必须是偶数；若当前 $n$ 是奇数（不能被 $2$ 整除），则 $x$ 也必须是奇数。

输入格式

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

每个测试用例占一行，包含两个整数 $n$ 和 $k$（$3 \le k \le n \le 10^{18}$，且 $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$（偶校验）的操作。

塞西莉亚期待你的帮助，通过智慧和策略，帮助她解开这个数学谜题，同时也让她的日常生活更加丰富多彩。