題目背景

諸多趣味項目告一段落，會場迎來了中場休息的茶話會。眾人閒談間聊起了科研的艱辛與論文投稿的不易：小 T 感慨自己每次投稿後都會不斷撤回重投、反覆打磨論文；而作為審稿人的小 S 則表示，自己審閱時必然會嚴格把關，盡可能篩除手上的稿件。

根據這番交流，小 T 和小 S 突發奇想：如果遇到一位極其苛刻的審稿人，論文的發表之路會演變成什麼樣？於是，他們順勢提出了一個博弈模型。在這個模型中，雙方將分別扮演投稿人與審稿人，圍繞一個漫長的審稿隊列展開博弈。隊列中混雜著大量他人的稿件，其中僅有一篇是投稿人投出的。投稿人希望讓自己的這篇論文在隊列中反覆循環打磨，以盡可能提升其最終發表時的學術分值；而審稿人則會嚴苛地篩查，尋找機會直接斃掉這篇論文，讓投稿人顆粒無收。

題目描述

審稿隊列由 $n$ 篇論文組成，其中第 $m$ 篇是投稿人投出的論文。初始時，該篇論文的學術分值為 $1$。

博弈由投稿人率先行動，之後雙方輪流進行。每次行動的一方需要依次執行以下操作：

1. 從審稿隊列首部依次取出 $k$ 篇論文。若隊列中剩餘論文不足 $k$ 篇，則將它們全部取出；
2. 在這批取出的論文中，選擇將其中的 $0$ 或 $1$ 篇論文發表或者永久拒稿，即將其徹底移除；
3. 將所有未被移除的論文以任意順序重新插入審稿隊列末尾。由於審稿隊列全程公開，雙方均能準確知曉重新插入後每篇論文的新位置。

投稿人的最終得分將由他投出的論文的結果決定：

• 每次行動中，若該篇論文未被移除且被重新插入審稿隊列末尾，其學術分值將會增加 $1$；
• 若投稿人在某次操作中主動移除了該篇論文，則該篇論文成功發表，博弈立即結束，投稿人獲得此時的學術分值；
• 若審稿人在某次操作中移除了該篇論文，則該篇論文被永久拒稿，博弈立即結束，投稿人獲得 $0$ 分。

投稿人的目標自然是最大化得分，而審稿人的目標是最小化投稿人的得分。

小 T 和小 S 目睹了你在前一場對弈遊戲中的優異表現，於是邀請你來分析這個有趣的博弈模型。你需要計算出，當投稿人與審稿人均採取最優策略時，投稿人的最終得分。要是你能幫他們算出結果，說不定他們會樂意親自幫你修改論文哦！

輸入格式

每個測試點中包含多組測試數據。輸入的第一行包含一個正整數 $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