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.

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.

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