審稿キューは $n$ 本の論文で構成されており、そのうち $m$ 番目の論文が投稿者によって提出されたものです。初期状態において、この論文の学術スコアは $1$ です。

ゲームは投稿者が先攻で始まり、その後両者が交互に行動します。各行動において、手番のプレイヤーは以下の操作を順に行う必要があります。

1. 審稿キューの先頭から順に $k$ 本の論文を取り出す。キュー内の残りの論文が $k$ 本未満の場合は、それらすべてを取り出す。
2. 取り出した論文の中から、$0$ 本または $1$ 本の論文を選択して発表または永久拒絶し、キューから完全に削除する。
3. 削除されなかったすべての論文を、任意の順序で審稿キューの末尾に再挿入する。審稿キューは常に公開されているため、両者は再挿入後の各論文の新しい位置を正確に把握できる。

投稿者の最終スコアは、提出した論文の結果によって決まります。

• 各行動において、その論文が削除されず、かつ審稿キューの末尾に再挿入された場合、その学術スコアは $1$ 増加する。
• 投稿者が自身の操作でその論文を削除した場合、その論文は受理され、ゲームは直ちに終了し、投稿者はその時点の学術スコアを獲得する。
• 審稿者が自身の操作でその論文を削除した場合、その論文は永久拒絶され、ゲームは直ちに終了し、投稿者は $0$ 点を獲得する。

投稿者の目的はスコアを最大化することであり、審稿者の目的は投稿者のスコアを最小化することです。

投稿者と審稿者がともに最適戦略をとる場合、投稿者の最終スコアを計算してください。

入力

各テストケースには複数のデータセットが含まれます。入力の最初の行には、データセットの数を示す正の整数 $T$ ($1 \le T \le 50$) が含まれます。各データセットについて：

• 1行目に3つの正の整数 $n, k, m$ ($1 \le n, k \le 10^9, 1 \le m \le n$) が与えられ、それぞれ審稿キューの長さ、一度に取り出す論文数、初期状態における投稿者の論文の位置を表します。

出力

各データセットについて、投稿者の最終スコアを1行に出力してください。なお、ゲームが終了しない場合は $-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