406942: GYM102623 A Archmage

Archmage (AM for short) is a hero unit in WatercraftⅢ.

He has $$$n$$$ mana at most and two powerful skills which enable him to show great strength in battle:

1. Use $$$x$$$ mana to summon a Water Element.
2. Brilliance Aura restores $$$y$$$ mana for AM in a second, and it is the only way to restore mana. Since his mana cannot exceed the upper limit, the superfluous mana will dissipate. i.e., suppose you have $$$p$$$ mana before the restoration, your mana will become $$$\min(p+y,n)$$$.

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.