C. Военная стратегия
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Разразилась война! Вы, как главный генерал страны, должны разработать стратегию размещения своих войск.

В ряд расположено $$$n$$$ баз, из которых $$$k$$$-я является домашней базой вашей армии. Изначально на базе $$$k$$$ находится только один солдат. Каждый день происходит следующее по порядку:

  • Вы отдаете приказ, выбирая базу $$$i$$$ ($$$1 \leq i \leq n$$$) и любое количество солдат внутри этой базы (в том числе вы можете выбрать $$$0$$$ или всех солдат, находящихся на этой базе в данный момент). Затем вы говорите всем солдатам, которым вы отдали приказ, либо переместиться на базу $$$i-1$$$, либо на базу $$$i+1$$$. Все солдаты должны двигаться в одном направлении, и ни один солдат не может перемещаться влево от базы $$$1$$$ или вправо от базы $$$n$$$.
  • Затем на базу $$$k$$$ приходит новый солдат. На этого солдата приказ этого дня не может распространяться.

Однако времени мало, и у вас есть только $$$m$$$ дней до атаки врага. База называется укреплённой, если в ней находится хотя бы один солдат. Ваша задача — найти максимальное количество укреплённых баз (включая домашнюю базу), которые вы можете иметь к концу $$$m$$$-го дня.

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

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

Первая строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$m$$$, $$$k$$$ ($$$1 \leq k \leq n \leq 10^5$$$, $$$1 \leq m \leq 10^9$$$) — количество баз, количество дней, которые у вас есть для укрепления ваших баз, и индекс домашней базы.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2\cdot 10^5$$$.

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

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

Пример
Входные данные
7
3 1 3
3 3 2
4 2 2
3 2 1
4 3 3
7 7 4
100000 1000000000 100000
Выходные данные
2
3
3
2
3
6
100000
Примечание

Во втором наборе входных данных вот один из способов, как вы можете укрепить $$$3$$$ базы:

  • В первый день прикажите $$$0$$$ солдатам на базе $$$3$$$ переместиться на базу $$$2$$$. В конце дня новый солдат приходит на базу $$$2$$$ (теперь на базе $$$2$$$ находится $$$2$$$ солдата, а на других базах — $$$0$$$ солдат).
  • На второй день прикажите $$$1$$$ солдату с базы $$$2$$$ переместиться на базу $$$1$$$. В конце дня новый солдат приходит на базу $$$2$$$. Теперь на базе $$$2$$$ находится $$$2$$$ солдата, а на базе $$$1$$$ — $$$1$$$ солдат.
  • На третий день прикажите $$$2$$$ солдатам с базы $$$2$$$ переместиться на базу $$$3$$$. В конце дня новый солдат приходит на базу $$$2$$$. Теперь на базе $$$1$$$ и $$$2$$$ находится по $$$1$$$ солдату, а на базе $$$3$$$ — $$$2$$$ солдата.
  • Теперь на каждой из баз $$$1$$$, $$$2$$$, $$$3$$$ находится по крайней мере один солдат. Следовательно, ответ — $$$3$$$.

В третьем наборе входных данных вот один из способов, как вы можете добиться укрепления $$$3$$$ баз:

  • В первый день прикажите существующему солдату переместиться с базы $$$2$$$ на базу $$$3$$$. В конце дня новый солдат приходит на базу $$$2$$$.
  • Во второй день прикажите солдату на базе $$$2$$$ переместиться на базу $$$1$$$. В конце дня новый солдат приходит на базу $$$2$$$.
  • Теперь на каждой из баз $$$1,2,3$$$ находится солдат. Следовательно, ответ — $$$3$$$. Можно показать, что нельзя иметь более $$$3$$$ укреплённых баз к концу $$$2$$$ дня.

Ниже приведено наглядное объяснение.