eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Подавление мятежа

Подавление мятежа

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Группа пиратов сопровождает набор кораблей, плывущих друг за другом. Однако капитан пиратов начинает терять контроль над своими подопечными, и некоторые нелояльные к нему пираты готовы поднять мятеж. Как только на некотором корабле S количество верных пиратов становится меньше суммарного числа нелояльных пиратов на S, на предыдущем корабле (если S не первый), и на следующем корабле (если S не последний) в конвое, то нелояльные пираты с этих кораблей перебираются на S для его захвата. Для предотвращения вспышки мятежа капитан решил распределить верных и нелояльных к нему пиратов по кораблям таким образом, чтобы нелояльные к нему пираты не смогли захватить ни одного корабля. При этом на каждом корабле должен находиться как минимум один верный пират чтобы управлять им.

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

Первая строка содержит количество тестов. Каждый тест состоит из одной строки и содержит два целых числа n и k (1n15, nk40). Первое число - количество кораблей; второе число - общее количество пиратов (верных и нет) в конвое.

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

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

Пример

Входные данные #1
3
1 3
3 4
3 16
Выходные данные #1
1
1
5
Источник 2011 Benelux Algorithm Programming Contest, Preliminaries, Задача A