CF1839A.The Good Array

You are given two integers $n$ and $k$.

An array $a_1, a_2, \ldots, a_n$ of length $n$, consisting of zeroes and ones is good if for all integers $i$ from $1$ to $n$ both of the following conditions are satisfied:

• at least $\lceil \frac{i}{k} \rceil$ of the first $i$ elements of $a$ are equal to $1$,
• at least $\lceil \frac{i}{k} \rceil$ of the last $i$ elements of $a$ are equal to $1$.

Here, $\lceil \frac{i}{k} \rceil$ denotes the result of division of $i$ by $k$, rounded up. For example, $\lceil \frac{6}{3} \rceil = 2$, $\lceil \frac{11}{5} \rceil = \lceil 2.2 \rceil = 3$ and $\lceil \frac{7}{4} \rceil = \lceil 1.75 \rceil = 2$.

Find the minimum possible number of ones in a good array.

给你两个整数 $n$ 和 $k$。

一个长度为 $n$ 的数组 $a_1, a_2, \ldots, a_n$（仅由 0 和 1 构成）被称为“好”的，当且仅当对所有从 $1$ 到 $n$ 的整数 $i$，以下两个条件均成立：

• 数组 $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 的最少可能个数。

Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The only line of each test case contains two integers $n$, $k$ ($2 \le n \le 100$, $1 \le k \le n$) — the length of array and parameter $k$ from the statement.

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。

每个测试用例仅有一行，包含两个整数 $n$、$k$（$2 \le n \le 100$，$1 \le k \le n$）—— 分别为数组长度及题目描述中的参数 $k$。

For each test case output one integer — the minimum possible number of ones in a good array.

It can be shown that under the given constraints at least one good array always exists.

对于每个测试用例，输出一个整数——好数组中 1 的最小可能数量。

可以证明，在给定约束条件下，至少存在一个好数组。

In the first test case, $n = 3$ and $k = 2$:

• Array $[ \, 1, 0, 1 \, ]$ is good and the number of ones in it is $2$.
• Arrays $[ \, 0, 0, 0 \, ]$, $[ \, 0, 1, 0 \, ]$ and $[ \, 0, 0, 1 \, ]$ are not good since for $i=1$ the first condition from the statement is not satisfied.
• Array $[ \, 1, 0, 0 \, ]$ is not good since for $i=1$ the second condition from the statement is not satisfied.
• All other arrays of length $3$ contain at least $2$ ones.

Thus, the answer is $2$.

In the second test case, $n = 5$ and $k = 2$:

• Array $[ \, 1, 1, 0, 0, 1 \, ]$ is not good since for $i=3$ the second condition is not satisfied.
• Array $[ \, 1, 0, 1, 0, 1 \, ]$ is good and the number of ones in it is $3$.
• It can be shown that there is no good array with less than $3$ ones, so the answer is $3$.

In the third test case, $n = 9$ and $k = 3$:

• Array $[ \, 1, 0, 1, 0, 0, 0, 1, 0, 1 \, ]$ is good and the number of ones in it is $4$.
• It can be shown that there is no good array with less than $4$ ones, so the answer is $4$.

In the fourth test case, $n = 7$ and $k = 1$. The only good array is $[ \, 1, 1, 1, 1, 1, 1, 1\, ]$, so the answer is $7$.

在第一个测试用例中，$n = 3$ 且 $k = 2$：

• 数组 $[ \, 1, 0, 1 \, ]$ 是合法的，其中 1 的个数为 $2$。
• 数组 $[ \, 0, 0, 0 \, ]$、$[ \, 0, 1, 0 \, ]$ 和 $[ \, 0, 0, 1 \, ]$ 均不合法，因为当 $i=1$ 时，不满足题面中给出的第一条条件。
• 数组 $[ \, 1, 0, 0 \, ]$ 不合法，因为当 $i=1$ 时，不满足题面中给出的第二条条件。
• 所有其余长度为 $3$ 的数组均至少包含 $2$ 个 1。

因此，答案为 $2$。

在第二个测试用例中，$n = 5$ 且 $k = 2$：

• 数组 $[ \, 1, 1, 0, 0, 1 \, ]$ 不合法，因为当 $i=3$ 时，不满足第二条条件。
• 数组 $[ \, 1, 0, 1, 0, 1 \, ]$ 是合法的，其中 1 的个数为 $3$。
• 可以证明，不存在 1 的个数少于 $3$ 的合法数组，因此答案为 $3$。

在第三个测试用例中，$n = 9$ 且 $k = 3$：

• 数组 $[ \, 1, 0, 1, 0, 0, 0, 1, 0, 1 \, ]$ 是合法的，其中 1 的个数为 $4$。
• 可以证明，不存在 1 的个数少于 $4$ 的合法数组，因此答案为 $4$。

在第四个测试用例中，$n = 7$ 且 $k = 1$。唯一的合法数组是 $[ \, 1, 1, 1, 1, 1, 1, 1\, ]$，因此答案为 $7$。