Defense

You are the owner of a castle, and you must defeat incoming monsters.

The castle is located at coordinate $N$ on a one-dimensional path of length $N$. For $M$ seconds, one monster is spawned at coordinate $1$ every second. Monsters that have already been spawned move forward by $1$ coordinate every second.

When a monster reaches the castle, the castle is attacked, and that monster disappears. Every monster has health $H$, and your attack power is $K$.

Every second, you may choose one alive monster and deal $K$ damage to it. The monster's health decreases by $K$, and if its health becomes $0$ or less, that monster disappears.

You may attack a monster immediately after it is spawned. Also, if a monster moves to coordinate $N$ and you attack and defeat it at that moment, it is considered not to have attacked the castle.

You may keep attacking until there are no alive monsters left. In other words, even after the last monster is spawned, if there are still alive monsters, you may continue attacking.

To minimize the number of attacks on the castle, you want to defeat as many monsters as possible. Find the maximum number of monsters you can defeat.

The input is given in the following format.

$T$ $N_1\ M_1\ H_1\ K_1$ $N_2\ M_2\ H_2\ K_2$ $\vdots$ $N_T\ M_T\ H_T\ K_T$

For each test case, print the maximum number of monsters you can defeat.

• $1 \le T \le 100\,000$.
• $1 \le N,M,H,K \le 1\,000\,000\,000$.
• All input values are integers.