引言

肉体的眼睛闭合之时，心灵的眼睛方能张开

题目描述

穿越数字之门,做出路径上的难题,你才能有向无限定者询问的机会.在数字之路上,你与37需要共同完成一个数学题,这个数学题的规则是这样的:

• 你可以从 1 到 $k$ 中选择一个数 $x$ ,并将其从 $n$ 中减去.
• 选择的 $x$ 必须与当前 $n$ 的奇偶性相同——如果 $n$ 是偶数, $x$ 也必须是偶数；奇数同理。
• 37需要你的帮助，计算将 $n$ 变为 0 所需的最少操作次数。

输入格式

输入第一行包含一个整数$t$ (1≤t≤100) —— 测试用例的数量 .

接下来共 $t$ 行,每行包含两个整数 $n$ 和 $k$(3≤k≤n≤10¹⁸ ,且 $k$ 为奇数)

输出格式

对于每个测试用例,输出一个整数——代表 $n$ 变为 0 所需的最少操作次数

样例

输入数据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