P9213 [Beginner Contest #11] Transplanting Willows (Hard Version)

**This problem has exactly the same meaning as the Easy Version. The only differences are the constraints and the number of test cases contained in a single test point.** HG is walking to school out of boredom. Looking at the row of willows by the roadside, a strange question suddenly pops into his mind...

Suppose there are $n$ willow trees in total, and the distance between each adjacent pair is $x$. Now he needs to perform some operations on these trees so that, **while keeping the “starting point of these $n$ trees” unchanged**, the distance between any two adjacent trees becomes $y$ ($y > x$). The operations he is allowed to do are as follows: - Transplant a tree: move a tree from one position to another position. If you are confused about what “starting point unchanged” means, you can refer to the illustration in “Sample Explanation”. Obviously, operations cost physical effort, so HG wants to keep as many trees as possible in their original positions. Now HG wants to know: in order to achieve the goal that the distance between any two adjacent trees is $y$, at most how many trees can remain at their original positions. Please help him.

**This problem contains multiple test cases within a single test point.** The input has $T + 1$ lines. The first line contains an integer $T$, representing the number of test cases. The next $T$ lines each contain three integers $n, x, y$, representing the number of willows, the original spacing, and the desired spacing.

Output $T$ lines. Each line contains one integer, meaning for the corresponding test case, in order to achieve the goal that the distance between any two adjacent trees is $y$, the maximum number of trees that can stay in their original positions.

### Sample 1 Explanation  The squares in the figure represent trees. The first row shows the situation before adjustment, and the second row shows the situation after adjustment. The three marked green squares are the trees that do not need to be moved; all other trees need to be moved. ### Constraints For $100\%$ of the data, it is guaranteed that $1 \leq T \leq 10 ^ 5$, $1 \leq n \leq 10 ^ {18}$, $1 \leq x < y \leq 10 ^ 9$. Translated by ChatGPT 5