F. Checkers
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are playing the game of checkers, there are $$$n$$$ enemies pieces on a 1D straight line, each time you have to jump over $$$k$$$ pieces of the enemy to eat the next $$$k+1$$$th piece. After that piece is eaten, you take it's place and that piece also vanishes. Given $$$T$$$ queries, each time given a separate $$$n$$$,$$$k$$$, and your piece's starting position, find the maximum number of pieces of the enemy that you can eat starting at the given starting position. The starting position is ordered such that the position is the number of enemy pieces to the left of your piece.

Input

The first line contains one single integer $$$T$$$ ($$$1 \le T \le 10^5$$$).

On the next $$$T$$$ lines, each line contains three numbers $$$n$$$, $$$k$$$, $$$s$$$ ($$$1 \le n \le 10^{18}$$$, $$$0 \le k,s \le n$$$) - denoting the number of enemy pieces, jumping requirement, and the starting position in each of the queries.

—

Tests are numbered from $$$1-10$$$ and each test is worth $$$10$$$ points.

Tests $$$1-2$$$ satisfy $$$1 \le T \le 100, 1 \le n \le 500$$$.

Tests $$$3$$$ satisfy $$$k=1$$$.

Tests $$$4$$$ satisfy $$$k \lt =5$$$.

Tests $$$5$$$ satisfy $$$k \lt =10$$$.

Tests $$$6-10$$$ satisfy no additional constraints.

Output

Output $$$k$$$ numbers, for each query what is the maximum number of pieces of the enemy that you can eat.

Example
Input
3
6 1 2
8 3 1
91 5 54
Output
5
3
86
Note

For the first testcase, the answer is 5 since a possible sequence to operate is:

xxuxxxx

uxnxxxx

nxnuxxx

nxnnxux

nunnxnx

nnnnxnu

Supposing that u is your piece, x is the enemy pieces, and n are blank spaces. In this scenario, it is provable that you can't eat all 6 pieces.