A. Разделите мультимножество
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Мультимножество — это набор чисел, в котором могут быть равные элементы, и порядок чисел не имеет значения. Например, $$$\{2,2,4\}$$$ — мультимножество.

У вас есть мультимножество $$$S$$$. Изначально мультимножество содержит только одно положительное целое число $$$n$$$. То есть, $$$S=\{n\}$$$. Кроме того, задано положительное целое число $$$k$$$.

За одну операцию вы можете выбрать любое положительное целое число $$$u$$$ из $$$S$$$ и удалить одно вхождение $$$u$$$ из $$$S$$$. Затем вставить не более $$$k$$$ положительных целых чисел в $$$S$$$, чтобы сумма всех вставленных чисел была равна $$$u$$$.

Найдите минимальное количество операций, чтобы сделать $$$S$$$ состоящим из $$$n$$$ единиц.

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

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Единственная строка каждого набора входных данных содержит два целых числа $$$n,k$$$ ($$$1\le n\le 1000,2\le k\le 1000$$$).

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

Для каждого набора входных данных выведите одно целое число, которое является требуемым ответом.

Пример
Входные данные
4
1 5
5 2
6 3
16 4
Выходные данные
0
4
3
5
Примечание

Для первого набора входных данных изначально $$$S=\{1\}$$$, что уже удовлетворяет требованию. Поэтому нам не нужно делать ни одной операции.

Для второго набора входных данных изначально $$$S=\{5\}$$$. Мы можем применить следующие операции:

  • Выберите $$$u=5$$$, удалите $$$u$$$ из $$$S$$$ и вставьте $$$2,3$$$ в $$$S$$$. Теперь $$$S=\{2,3\}$$$.
  • Выберите $$$u=2$$$, удалите $$$u$$$ из $$$S$$$ и вставьте $$$1,1$$$ в $$$S$$$. Теперь $$$S=\{1,1,3\}$$$.
  • Выберите $$$u=3$$$, удалите $$$u$$$ из $$$S$$$ и вставьте $$$1,2$$$ в $$$S$$$. Теперь $$$S=\{1,1,1,2\}$$$.
  • Выберите $$$u=2$$$, удалите $$$u$$$ из $$$S$$$ и вставьте $$$1,1$$$ в $$$S$$$. Теперь $$$S=\{1,1,1,1,1\}$$$.

Используя $$$4$$$ операции в общей сложности, мы достигаем цели.

Для третьего набора входных данных изначально $$$S=\{6\}$$$. Мы можем применить следующие операции:

  • Выберите $$$u=6$$$, удалите $$$u$$$ из $$$S$$$ и вставьте $$$1,2,3$$$ в $$$S$$$. Теперь $$$S=\{1,2,3\}$$$.
  • Выберите $$$u=2$$$, удалите $$$u$$$ из $$$S$$$ и вставьте $$$1,1$$$ в $$$S$$$. Теперь $$$S=\{1,1,1,3\}$$$.
  • Выберите $$$u=3$$$, удалите $$$u$$$ из $$$S$$$ и вставьте $$$1,1,1$$$ в $$$S$$$. Теперь $$$S=\{1,1,1,1,1,1\}$$$.

Используя $$$3$$$ операции в общей сложности, мы достигаем цели.

Для четвертого набора входных данных изначально $$$S=\{16\}$$$. Мы можем применить следующие операции:

  • Выберите $$$u=16$$$, удалите $$$u$$$ из $$$S$$$ и вставьте $$$4,4,4,4$$$ в $$$S$$$. Теперь $$$S=\{4,4,4,4\}$$$.
  • Повторите $$$4$$$ раза: выберите $$$u=4$$$, удалите $$$u$$$ из $$$S$$$ и вставьте $$$1,1,1,1$$$ в $$$S$$$.

Используя $$$5$$$ операций в общей сложности, мы достигаем цели.