CF1860B.Fancy Coins

Monocarp is going to make a purchase with cost of exactly $m$ burles.

He has two types of coins, in the following quantities:

• coins worth $1$ burle: $a_1$ regular coins and infinitely many fancy coins;
• coins worth $k$ burles: $a_k$ regular coins and infinitely many fancy coins.

Monocarp wants to make his purchase in such a way that there's no change — the total worth of provided coins is exactly $m$. He can use both regular and fancy coins. However, he wants to spend as little fancy coins as possible.

What's the smallest total number of fancy coins he can use to make a purchase?

Monocarp 计划进行一次恰好花费 $m$ 布尔的购买。

他有两种类型的硬币，数量如下：

• 面值为 $1$ 布尔的硬币：有 $a_1$ 枚普通硬币，以及无限枚花式硬币；
• 面值为 $k$ 布尔的硬币：有 $a_k$ 枚普通硬币，以及无限枚花式硬币。

Monocarp 希望以不找零的方式完成这次购买——即所付硬币的总面值恰好为 $m$。他可以同时使用普通硬币和花式硬币。但他的目标是尽可能少地使用花式硬币。

那么，他完成此次购买所需使用的花式硬币的最小总数是多少？

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.

第一行包含一个整数 $t$（$1 \le t \le 3 \cdot 10^4$）—— 测试用例的数量。

每个测试用例仅一行，包含四个整数 $m, k, a_1$ 和 $a_k$（$1 \le m \le 10^8$；$2 \le k \le 10^8$；$0 \le a_1, a_k \le 10^8$）—— 分别表示购买的花费、第二种硬币的面值，以及两种硬币各自的初始数量。

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

对于每个测试用例，输出一个整数——Monocarp 为完成购买所需使用的华丽硬币的最小总数。

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.

在第一个测试用例中，两种类型的普通硬币数量均为 0。Monocarp 可以使用 $2$ 枚面值为 $1$ 卢布的精美硬币和 $3$ 枚面值为 $3$（因为 $k=3$）卢布的精美硬币，总共得到 $11$ 卢布，共使用 $5$ 枚精美硬币。

在第二个测试用例中，Monocarp 拥有大量两种类型的普通硬币。例如，他可以使用 $11$ 枚面值为 $1$ 卢布的普通硬币。注意：Monocarp 并不需要最小化所用硬币的总数。这样，他使用了 $0$ 枚精美硬币。

在第三个测试用例中，Monocarp 可以使用 $5$ 枚面值为 $1$ 卢布的普通硬币和 $1$ 枚面值为 $3$ 卢布的普通硬币，总计得到 $8$ 卢布，但其目标是 $11$ 卢布。因此，只需 $1$ 枚面值为 $3$ 卢布的精美硬币即可满足要求。