The Good Array
Description
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.
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.
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.
Input
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.
Output
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.
7
3 2
5 2
9 3
7 1
10 4
9 5
8 8
2
3
4
7
4
3
2
Note
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$.