#175 Defense

Statement

Statement language

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.

Input

The input is given in the following format.

$T$ $N_1\ M_1\ H_1\ K_1$

Output

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

Constraints

$1 \le T \le 100\,000$ .
$1 \le N,M,H,K \le 1\,000\,000\,000$ .

Subtasks

#	Score	Constraints
1	100	The full constraints apply.

Samples

Input

Output

1
2
0

In the first test case, the only monster can be defeated immediately.

In the second test case, each monster requires $2$ attacks, and both monsters can be defeated.

In the third test case, a monster requires $20$ attacks, but no monster can be attacked $20$ times before reaching the castle.