After many interesting projects concluded, the venue hosted a tea break. People chatted about the hardships of scientific research and the difficulties of submitting papers. Little T lamented that after every submission, they would constantly withdraw and resubmit, polishing the paper repeatedly. Little S, acting as a reviewer, remarked that they always strictly gatekeep during reviews, trying their best to filter out the manuscripts in their hands.

Based on this exchange, Little T and Little S had a sudden idea: what would the path to publishing a paper look like if one encountered an extremely harsh reviewer? Thus, they proposed a game model. In this model, both sides play the roles of the author and the reviewer, engaging in a game around a long review queue. The queue is mixed with a large number of other people's manuscripts, among which only one is the paper submitted by the author. The author hopes to let their paper circulate and be polished in the queue repeatedly to maximize its final academic score upon publication; the reviewer, however, will strictly screen the papers, looking for opportunities to directly reject this paper and leave the author with nothing.

The review queue consists of $n$ papers, where the $m$-th paper is the one submitted by the author. Initially, the academic score of this paper is $1$.

The game starts with the author moving first, and then both sides take turns. In each turn, the player whose turn it is must perform the following operations in order:

1. Take out $k$ papers from the front of the review queue one by one. If there are fewer than $k$ papers remaining in the queue, take them all out.
2. From the papers taken out, choose to publish or permanently reject $0$ or $1$ paper, which means removing it completely.
3. Re-insert all remaining papers into the end of the review queue in any order. Since the review queue is public throughout, both sides know exactly the new position of each paper after re-insertion.

The author's final score is determined by the result of their submitted paper:

• In each turn, if the paper has not been removed and is re-inserted at the end of the review queue, its academic score increases by $1$.
• If the author voluntarily removes the paper during an operation, the paper is successfully published, the game ends immediately, and the author receives the current academic score.
• If the reviewer removes the paper during an operation, the paper is permanently rejected, the game ends immediately, and the author receives a score of $0$.

The author's goal is to maximize their score, while the reviewer's goal is to minimize the author's score.

Little T and Little S witnessed your excellent performance in the previous game and invited you to analyze this interesting game model. You need to calculate the author's final score when both the author and the reviewer adopt their optimal strategies.

Input

Each test case contains multiple test data sets. The first line of the input contains a positive integer $T$ ($1 \le T \le 50$), representing the number of data sets. For each data set:

• The first line contains three positive integers $n, k, m$ ($1 \le n, k \le 10^9, 1 \le m \le n$), representing the length of the review queue, the number of papers taken out each time, and the initial position of the author's paper.

Output

For each test data set, output a single integer representing the author's final score. In particular, if the game does not end, output $-1$.

Examples

Input 1

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

Output 1

2
0
2
4
3470
278264358