单点时限: 2.0 sec
内存限制: 256 MB
Archmage (AM for short) is a hero unit in $\text{Watercraft}\ Ⅲ$.
He has $n$ mana at most and two powerful skills which enable him to show great strength in battle:
Since the power of an Archmage is tremendous, the upper limit of mana $n$ is always greater than or equal to $x+y$.
Every second, Archmage will summon exactly one Water Element (if the mana is enough, i.e., his mana won’t be less than $0$ after that) or do nothing. Then no matter what he did before, he will restore $y$ mana.
Archmage has $n$ mana at the end of the second $0$, and the game starts at the beginning of the second $1$.
He wants to know how many Water Elements he can summon at most before the end of the second $m$.
The input consists of multiple test cases.
The first line contains a single integer $t(1 \leq t \leq 10^5)$, indicating the number of test cases.
Each of the next $t$ lines contains $4$ integers $n,m,x,y(1 \leq m,x,y \leq 10^9,x+y \leq n \leq 2 \times 10^9)$.
For each test case, output the answer in a line.
3 2 2 1 1 4 4 2 1 6 10 4 2
2 3 6
In test case $1$, Archmage can cast spells every second, so the answer is $2$.
In test case $2$, here’s a way for Archmage to cast spells $3$ times.
Second $1$: Archmage cast spells, and there is $4-x+y=3$ mana left.
Second $2$: Archmage cast spells, and there is $3-x+y=2$ mana left.
Second $3$: Archmage cast spells, and there is $2-x+y=1$ mana left.
Second $4$: Archmage doesn’t have enough mana so he can do nothing, and there is $1+y=2$ mana left.