배경

여러 재미있는 프로젝트가 끝나고, 대회장에는 중간 휴식 시간을 위한 다과회가 열렸습니다. 사람들은 담소를 나누며 연구의 고충과 논문 투고의 어려움에 대해 이야기했습니다. 소 T는 논문을 투고할 때마다 계속해서 철회하고 다시 투고하며 논문을 반복해서 다듬어야 했던 경험을 토로했고, 심사위원인 소 S는 자신이 심사할 때 반드시 엄격하게 검토하여 가능한 한 많은 원고를 걸러내려 한다고 말했습니다.

이 대화를 바탕으로 소 T와 소 S는 기발한 생각을 떠올렸습니다. 만약 매우 까다로운 심사위원을 만난다면 논문의 발표 과정은 어떻게 변할까? 그래서 그들은 게임 이론 모델을 제안했습니다. 이 모델에서 양측은 각각 투고자와 심사위원을 맡아 긴 심사 대기열을 두고 게임을 진행합니다. 대기열에는 다른 사람들의 원고가 많이 섞여 있으며, 그중 단 하나만이 투고자가 투고한 논문입니다. 투고자는 자신의 논문이 대기열에서 반복적으로 순환하며 다듬어지기를 바라며, 이를 통해 최종 발표 시의 학술 점수를 최대한 높이고자 합니다. 반면 심사위원은 엄격하게 심사하여 이 논문을 직접 제거할 기회를 찾아 투고자가 아무런 성과도 얻지 못하게 하려 합니다.

문제 설명

심사 대기열은 $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