Fancy Coins

Description:

Input:

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 3 \cdot 10^4$$$) — the number of testcases.

The only line of each testcase contains four integers $$$m, k, a_1$$$ and $$$a_k$$$ ($$$1 \le m \le 10^8$$$; $$$2 \le k \le 10^8$$$; $$$0 \le a_1, a_k \le 10^8$$$) — the cost of the purchase, the worth of the second type of coin and the amounts of regular coins of both types, respectively.

Output:

For each testcase, print a single integer — the smallest total number of fancy coins Monocarp can use to make a purchase.

Sample Input:

4
11 3 0 0
11 3 20 20
11 3 6 1
100000000 2 0 0

Sample Output:

5
0
1
50000000

Note:

In the first testcase, there are no regular coins of either type. Monocarp can use $$$2$$$ fancy coins worth $$$1$$$ burle and $$$3$$$ fancy coins worth $$$3$$$ (since $$$k=3$$$) burles to get $$$11$$$ total burles with $$$5$$$ total fancy coins.

In the second testcase, Monocarp has a lot of regular coins of both types. He can use $$$11$$$ regular coins worth $$$1$$$ burle, for example. Notice that Monocarp doesn't have to minimize the total number of used coins. That way he uses $$$0$$$ fancy coins.

In the third testcase, Monocarp can use $$$5$$$ regular coins worth $$$1$$$ burle and $$$1$$$ regular coin worth $$$3$$$ burles. That will get him to $$$8$$$ total burles when he needs $$$11$$$. So, $$$1$$$ fancy coin worth $$$3$$$ burles is enough.