Очередной проект завершен, и в конференц-зале начался кофе-брейк. В ходе непринужденной беседы участники заговорили о трудностях научной работы и публикации статей: Сяо Т. посетовал, что после каждой подачи ему приходится постоянно отзывать и переподавать статью, бесконечно дорабатывая её; а Сяо С., выступающий в роли рецензента, отметил, что при проверке он всегда проявляет строгость, стараясь отсеять как можно больше рукописей.

Вдохновившись этим разговором, Сяо Т. и Сяо С. решили пофантазировать: что, если бы на пути статьи встретился крайне придирчивый рецензент? Так они предложили игровую модель. В этой модели стороны выступают в роли автора и рецензента, соревнуясь вокруг длинной очереди на рецензирование. В очереди смешано множество чужих рукописей, и лишь одна из них принадлежит автору. Автор хочет, чтобы его статья как можно дольше циркулировала в очереди, дорабатываясь и повышая свою академическую ценность, в то время как рецензент стремится строго проверять статьи и найти возможность отклонить именно эту работу, оставив автора ни с чем.

Очередь на рецензирование состоит из $n$ статей, где $m$-я статья — это работа автора. Изначально академическая ценность этой статьи равна 1.

Игра начинается с хода автора, после чего стороны ходят по очереди. В свой ход игрок должен последовательно выполнить следующие действия:

1. Извлечь из начала очереди $k$ статей. Если в очереди осталось меньше $k$ статей, извлекаются все оставшиеся.
2. Из этой группы извлеченных статей выбрать 0 или 1 статью для публикации или окончательного отклонения, то есть полностью удалить её из процесса.
3. Все оставшиеся не удаленными статьи в произвольном порядке вставить в конец очереди на рецензирование. Поскольку очередь полностью открыта, обе стороны точно знают новые позиции каждой статьи после перестановки.

Итоговый счет автора определяется результатом его статьи:

• Если в ходе операции статья не была удалена и была вставлена в конец очереди, её академическая ценность увеличивается на 1.
• Если автор в ходе своего хода добровольно удалил свою статью, она считается успешно опубликованной, игра немедленно заканчивается, и автор получает текущую академическую ценность.
• Если рецензент в ходе своего хода удалил статью автора, она считается окончательно отклоненной, игра немедленно заканчивается, и автор получает 0 очков.

Цель автора — максимизировать свой счет, а цель рецензента — минимизировать его.

Сяо Т. и Сяо С. стали свидетелями твоего блестящего выступления в предыдущей игре и пригласили тебя проанализировать эту интересную модель. Тебе нужно вычислить итоговый счет автора, если обе стороны придерживаются оптимальной стратегии. Если ты поможешь им найти результат, возможно, они с радостью помогут тебе отредактировать твою статью!

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

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

• Первая строка содержит три целых числа $n, k, m$ ($1 \le n, k \le 10^9, 1 \le m \le n$), представляющие длину очереди, количество извлекаемых статей и начальную позицию статьи автора соответственно.

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

Для каждого набора данных выведите одно целое число — итоговый счет автора. В частности, если игра никогда не заканчивается, выведите $-1$.

Примеры

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

6
3 2 1
5 3 4
10 3 1
7 3 7
817247666 7237 327476688
610723117 332458760 292738094

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

2
0
2
4
3470
278264358