Выезд с дачного участка огорожен забором, состоящим из $$$n$$$ досок, шириной $$$1$$$ метр. Слева и справа от выезда находятся заборы других участков. Некоторые из досок забора хотят вытащить для строительства бани (возможно, все или ни одной), при этом на даче есть автоматическая газонокосилка шириной $$$w$$$ метров, которая не должна покинуть участок через дыру в заборе.
Газонокосилка сможет выехать за пределы участка, если среди номеров вытащенных досок будет хотя бы $$$w$$$ подряд идущих. Определите максимальное количество досок, которое можно вытащить из забора.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Единственная строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$w$$$ ($$$1 \leq n \leq 10^{9}$$$, $$$1 \leq w \leq 10^{9}$$$) — количество досок в заборе и ширину газонокосилки в метрах соответственно.
Для каждого набора входных данных выведите единственное число — максимальное количество досок, которое можно вытащить из забора.
59 313 415 1420 11000 42
610140977
В первом наборе входных данных забор состоит из $$$9$$$ досок.
Можно вынуть $$$6$$$ досок и оставить только доски с номерами $$$2$$$, $$$5$$$ и $$$8$$$. Тогда газонокосилка не сможет покинуть пределы территории.
Во втором наборе входных данных можно вытащить $$$10$$$ досок, возможный пример расположения представлен ниже.
| Codeforces Round 1078 (Div. 2) |
|---|
| Закончено |
