A. Хороший массив
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны целые числа $$$n$$$ и $$$k$$$.

Назовем массив $$$a_1, a_2, \ldots, a_n$$$ длины $$$n$$$, состоящий из нулей и единиц, хорошим, если для всех целых $$$i$$$ от $$$1$$$ до $$$n$$$ выполняются оба следующих условия:

  • среди первых $$$i$$$ элементов $$$a$$$ хотя бы $$$\lceil \frac{i}{k} \rceil$$$ равны $$$1$$$,
  • среди последних $$$i$$$ элементов $$$a$$$ хотя бы $$$\lceil \frac{i}{k} \rceil$$$ равны $$$1$$$.

Здесь $$$\lceil \frac{i}{k} \rceil$$$ обозначает результат деления $$$i$$$ на $$$k$$$, округлённый вверх. Например, $$$\lceil \frac{6}{3} \rceil = 2$$$, $$$\lceil \frac{11}{5} \rceil = \lceil 2.2 \rceil = 3$$$ и $$$\lceil \frac{7}{4} \rceil = \lceil 1.75 \rceil = 2$$$.

Найдите наименьшее возможное количество единиц в хорошем массиве.

Входные данные

В первой строке задано целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следуют описания этих наборов.

В первой строке даны два целых числа $$$n$$$, $$$k$$$ ($$$2 \le n \le 100$$$, $$$1 \le k \le n$$$) — длина массива и параметр $$$k$$$ из условия.

Выходные данные

Для каждого набора входных данных выведите одно число — наименьшее возможное количество единиц в хорошем массиве.

Можно показать, что при данных ограничениях всегда существует хотя бы один хороший массив.

Пример
Входные данные
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 \, ]$$$ является хорошим и количество единиц в нём равно $$$2$$$.
  • Массивы $$$[ \, 0, 0, 0 \, ]$$$, $$$[ \, 0, 1, 0 \, ]$$$ и $$$[ \, 0, 0, 1 \, ]$$$ не являются хорошими, так как для этих массивов при $$$i=1$$$ не выполняется первое условие.
  • Массив $$$[ \, 1, 0, 0 \, ]$$$ не является хорошим, так как для него при $$$i=1$$$ не выполняется второе условие.
  • Во всех остальных массивах длины $$$3$$$ есть хотя бы $$$2$$$ единицы.

Таким образом, ответ равен $$$2$$$.

Во втором наборе входных данных $$$n = 5$$$ и $$$k = 2$$$:

  • Массив $$$[ \, 1, 1, 0, 0, 1 \, ]$$$ не является хорошим, так как для него при $$$i=3$$$ не выполняется второе условие.
  • Массив $$$[ \, 1, 0, 1, 0, 1 \, ]$$$ является хорошим и количество единиц в нём равно $$$3$$$.
  • Можно показать, что хорошего массива, содержащего меньше $$$3$$$ единиц, не существует, поэтому ответ равен $$$3$$$.

В третьем наборе входных данных $$$n = 9$$$ и $$$k = 3$$$:

  • Массив $$$[ \, 1, 0, 1, 0, 0, 0, 1, 0, 1 \, ]$$$ является хорошим и количество единиц в нём равно $$$4$$$.
  • Можно показать, что хорошего массива, содержащего меньше $$$4$$$ единиц, не существует, поэтому ответ равен $$$4$$$.

В четвертом наборе входных данных $$$n = 7$$$ и $$$k = 1$$$. Существует единственный хороший массив $$$[ \, 1, 1, 1, 1, 1, 1, 1\, ]$$$, поэтому ответ равен $$$7$$$.