A. The Good Arraytime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou 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.InputEach 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.OutputFor 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
73 25 29 37 110 49 58 8Output
2
3
4
7
4
3
2
NoteIn 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.
73 25 29 37 110 49 58 8
2 3 4 7 4 3 2 
['greedy', 'implementation', 'math', '*800']