# 2020 年 “联想杯”全国高校程序设计在线邀请赛暨第三届上海理工大学程序设计竞赛

A. Archmage
PDF 题面可用

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:

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.

### 样例

Input
3
2 2 1 1
4 4 2 1
6 10 4 2

Output
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.

NaN