F. Исследование
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Исследовать: возьмите карты из одной из закрытых колод в количестве, равном вашему показателю исследования. Вы можете выбрать одну карту: Построить или Сохранить.

Алиса и Боб играют в игру с колодой карт. Эта колода состоит из $$$n-1$$$ белых карт и одной зелёной карты. Изначально зелёная карта находится на $$$s$$$-м месте сверху колоды, и на ней написано число $$$1$$$. И Алиса, и Боб знают, где находится зелёная карта.

Алиса ходит первой. На каждом ходу они должны действовать следующим образом:

  • Взять $$$k$$$ карт сверху колоды. (Если в колоде меньше чем $$$k$$$ карт, взять все карты.) После этого выбросить $$$0$$$ или $$$1$$$ карту среди этих $$$k$$$ карт и положить оставшиеся карты в нижнюю часть колоды в любом порядке.
  • Если Боб выбрасывает зелёную карту, игра немедленно заканчивается, а счёт равен $$$0$$$.
  • Если Алиса выбрасывает зелёную карту, игра немедленно заканчивается, а счёт равен числу, написанному на зелёной карте.
  • Если Алиса берёт зелёную карту и возвращает её в колоду, она должна сообщить Бобу новое положение зелёной карты и увеличить число на зелёной карте на $$$1$$$.

Алиса должна максимизировать счёт, а Боб — минимизировать его. Требуется найти итоговый счёт игры, если оба играют оптимально.

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

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

В единственной строке каждого набора входных данных содержатся три целых числа $$$n$$$, $$$k$$$ и $$$s$$$ ($$$1\le n,k\le 10^9$$$, $$$1\le s\le n$$$).

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

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

Пример
Входные данные
6
3 2 1
5 3 4
10 3 1
7 3 7
817247666 7237 327476688
610723117 332458760 292738094
Выходные данные
2
0
2
4
3470
278264358
Примечание

В первом наборе входных данных оптимальный ход игры выглядит так. Алиса должна взять $$$2$$$ карты сверху, ничего не выбрасывать и вернуть зелёную карту в нижнюю часть колоды. Затем Боб должен взять $$$2$$$ белые карты сверху и выбросить одну. На третьем ходу Алиса должна выбросить зелёную карту с числом $$$2$$$.

Во втором наборе входных данных Боб первым возьмёт зелёную карту и выбросит её. Поэтому счёт должен быть равен $$$0$$$.