给你两个整数 $$$n$$$ 和 $$$k$$$。
如果对于从 $$$1$$$ 到 $$$n$$$ 的所有整数 $$$i$$$ 满足以下两个条件,则长度为 $$$n$$$ 且由零和一组成的数组 $$$a_1, a_2, \ldots, a_n$$$ 是好的:
- $$$a$$$ 的前 $$$i$$$ 元素至少 $$$\lceil \frac{i}{k} \rceil$$$ 等于 $$$1$$$,
- $$$a$$$ 的最后 $$$i$$$ 元素至少 $$$\lceil \frac{i}{k} \rceil$$$ 等于 $$$1$$$。
这里, $$$\lceil \frac{i}{k} \rceil$$$ 表示 $$$i$$$ 除以 $$$k$$$ 的结果,向上舍入。例如,$$$\lceil \frac{6}{3} \rceil = 2$$$、$$$\lceil \frac{11}{5} \rceil = \lceil 2.2 \rceil = 3$$$ 和 $$$\lceil \frac{7}{4} \rceil = \lceil 1.75 \rceil = 2$$$。
找出一个好的数组中 1 的最小可能数量。
输入
每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例的唯一行包含两个整数 $$$n$$$, $$$k$$$ ($$$2 \le n \le 100$$$, $$$1 \le k \le n$$$) - 语句中数组和参数 $$$k$$$ 的长度。
输出
对于每个测试用例,输出一个整数——一个好的数组中可能存在的最小数量。
可以证明,在给定的约束下,至少总是存在一个好的数组。
示例
输入 #1
7 3 2 5 2 9 3 7 1 10 4 9 5 8 8
输出 #1
2 3 4 7 4 3 2
注意
在第一个测试用例中,$$$n = 3$$$ 和 $$$k = 2$$$:
- 数组 $$$[ \, 1, 0, 1 \, ]$$$ 很好,其中的个数是 $$$2$$$。
- 数组 $$$[ \, 0, 0, 0 \, ]$$$, $$$[ \, 0, 1, 0 \, ]$$$ 和 $$$[ \, 0, 0, 1 \, ]$$$ 不好,因为对于 $$$i=1$$$ 语句中的第一个条件不满足。
- 数组 $$$[ \, 1, 0, 0 \, ]$$$ 不好,因为对于 $$$i=1$$$ 语句中的第二个条件不满足。
- 所有其他长度为 $$$3$$$ 的数组至少包含 $$$2$$$ 个。
因此,答案是$$$2$$$。
在第二个测试用例中,$$$n = 5$$$ 且 $$$k = 2$$$:
- 数组 $$$[ \, 1, 1, 0, 0, 1 \, ]$$$ 不好,因为对于 $$$i=3$$$ 不满足第二个条件。
- 数组 $$$[ \, 1, 0, 1, 0, 1 \, ]$$$ 很好,其中的个数是 $$$3$$$。
- 可以证明,没有小于 $$$3$$$ 的好数组,所以答案是 $$$3$$$。
在第三个测试用例中,$$$n = 9$$$ 且 $$$k = 3$$$:
- 数组 $$$[ \, 1, 0, 1, 0, 0, 0, 1, 0, 1 \, ]$$$ 很好,其中的个数是 $$$4$$$。
- 可以证明,没有小于 $$$4$$$ 的好数组,所以答案是 $$$4$$$。
在第四个测试用例中,$$$n = 7$$$ 和 $$$k = 1$$$。唯一好的数组是 $$$[ \, 1, 1, 1, 1, 1, 1, 1\, ]$$$,所以答案是 $$$7$$$。