310471: CF1839A. The Good Array

A. The Good Arraytime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

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.

ExampleInput

7
3 2
5 2
9 3
7 1
10 4
9 5
8 8

Output

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$.

题目大意：
给定两个整数n和k，定义一个长度为n的由0和1组成的数组a为“好的”，如果对于所有整数i从1到n，以下两个条件都满足：
1. 数组a的前i个元素中至少有⌈i/k⌉个等于1，
2. 数组a的后i个元素中至少有⌈i/k⌉个等于1。
求一个“好的”数组中1的最小可能数量。

输入输出数据格式：
输入：
- 第一行包含一个整数t（1≤t≤10^4），表示测试用例的数量。
- 每个测试用例包含一行，有两个整数n, k（2≤n≤100，1≤k≤n），分别表示数组的长度和参数k。

输出：
- 对于每个测试用例，输出一行，包含一个整数，表示“好的”数组中1的最小可能数量。

示例：
输入：
```
7
3 2
5 2
9 3
7 1
10 4
9 5
8 8
```
输出：
```
2
3
4
7
4
3
2
```

注意：
- 在第一个测试用例中，n=3和k=2，数组[1,0,1]是好的，且1的数量是2。其他所有长度为3的数组都至少包含2个1，所以答案是2。
- 在第二个测试用例中，n=5和k=2，数组[1,0,1,0,1]是好的，且1的数量是3。可以证明没有包含少于3个1的好数组，所以答案是3。
- 在第三个测试用例中，n=9和k=3，数组[1,0,1,0,0,0,1,0,1]是好的，且1的数量是4。可以证明没有包含少于4个1的好数组，所以答案是4。
- 在第四个测试用例中，n=7和k=1，唯一的好数组是[1,1,1,1,1,1,1]，所以答案是7。题目大意： 给定两个整数n和k，定义一个长度为n的由0和1组成的数组a为“好的”，如果对于所有整数i从1到n，以下两个条件都满足： 1. 数组a的前i个元素中至少有⌈i/k⌉个等于1， 2. 数组a的后i个元素中至少有⌈i/k⌉个等于1。 求一个“好的”数组中1的最小可能数量。 输入输出数据格式： 输入： - 第一行包含一个整数t（1≤t≤10^4），表示测试用例的数量。 - 每个测试用例包含一行，有两个整数n, k（2≤n≤100，1≤k≤n），分别表示数组的长度和参数k。 输出： - 对于每个测试用例，输出一行，包含一个整数，表示“好的”数组中1的最小可能数量。 示例： 输入： ``` 7 3 2 5 2 9 3 7 1 10 4 9 5 8 8 ``` 输出： ``` 2 3 4 7 4 3 2 ``` 注意： - 在第一个测试用例中，n=3和k=2，数组[1,0,1]是好的，且1的数量是2。其他所有长度为3的数组都至少包含2个1，所以答案是2。 - 在第二个测试用例中，n=5和k=2，数组[1,0,1,0,1]是好的，且1的数量是3。可以证明没有包含少于3个1的好数组，所以答案是3。 - 在第三个测试用例中，n=9和k=3，数组[1,0,1,0,0,0,1,0,1]是好的，且1的数量是4。可以证明没有包含少于4个1的好数组，所以答案是4。 - 在第四个测试用例中，n=7和k=1，唯一的好数组是[1,1,1,1,1,1,1]，所以答案是7。