CF1839A The Good Array

对于一个由 $0$ 和 $1$ 构成的数组 $a_1,a_2,\dots,a_n$，如果对于从 $1$ 到 $n$ 中所有的整数 $i$ 都满足以下两个条件，我们称这个数组为『好的数组』： - **前** $i$ 个元素中有至少 $\left\lceil\frac{i}{k}\right\rceil$ 个元素为 $1$； - **后** $i$ 个元素中有至少 $\left\lceil\frac{i}{k}\right\rceil$ 个元素为 $1$。 其中，$\left\lceil\frac{i}{k}\right\rceil$ 表示 $i$ 除以 $k$ 向上取整。 构造一个长度为 $n$ 的『好的数组』，使其中 $1$ 的数量尽可能的少。

本题多测。第一行为一个整数 $t\left(1\le t\le10^4\right)$，表示有 $t$ 组数据。

每组样例输出一行一个整数，表示你构造的『好的数组』中 $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 $ .