The Cinema Layout

Input

The first line contains a single integer $t$ (1 \le t \le 10^4) — the number of test cases.

Each of the next $t$ lines contains three integers $m$, $n$, and $s$ (1 \le m, n, s \le 10^{18}) — the number of seats per row, the number of consecutive seats to book, and the starting seat number, respectively.

Output

For each test case, output a single integer — the total number of distinct rows occupied by Fady's group.

Examples

Note

In the first test case, there are $3$ seats per row. Fady books $5$ seats starting at seat $2$. The booked seats are 2, 3, 4, 5, and $6$.

• Seats $2$ and $3$ are in row $1$.

• Seats $4,5,$ and $6$ are in row $2$.

The group occupies $2$ distinct rows in total.

Scoring

• Subtask $1$ ($20$ points): \sum n \le 10^5 across all test cases.

• Subtask $2$ ($80$ points): No additional constraints.