你刚刚开始在边防部队服兵役。由于你是一名计算机科学专业的毕业生，他们要求你为士兵制定一份值勤表。最初，没有任何士兵在岗，你需要制定一份满足以下两个要求的排班表：

• 共有 $N$ 名士兵，每名士兵最多连续值勤 $K$ 个月，之后必须休假一个月。
• 排班表需要确保在任何给定时间内，在岗的士兵人数的最小值最大化。

给定 $N$ 和 $K$，系统将计算在任何给定时间内，能够保证在岗的士兵人数的最大值。

输入格式

你的程序将在一个或多个测试用例上进行测试。输入的第一行是一个整数 $T$，表示测试用例的数量 ($1 \le T \le 100$)。

每个测试用例包含一行，由两个空格分隔的整数组成：

• $N$：士兵的总人数 ($0 \le N \le 10,000,000$)。
• $K$：士兵在必须休假一个月之前可以连续值勤的月数 ($0 \le K \le 10,000,000$)。

输出格式

对于每个测试用例，输出一行，包含在任何给定时间内，能够保证在岗的士兵人数的最大值。

样例

输入 1

3
4 1
9 3
21 3

输出 1

2
6
15