题目描述

贝茜奶牛拥有 A 个 A 型筹码和 B 个 B 型筹码（0 ≤ A, B ≤ 10⁹）。

她可以无限次执行以下操作：

若当前拥有的 B 型筹码数量至少为 cB 个，则可以用 cB 个 B 型筹码兑换 cA 个 A 型筹码（1 ≤ cA, cB ≤ 10⁹）。

请确定最小的非负整数 x，使得满足以下条件：在额外获得 x 个随机筹码后，贝茜一定能通过操作最终拥有至少 fA 个 A 型筹码（0 ≤ fA ≤ 10⁹）。

输入格式（输入从终端 / 标准输入读取）

第一行包含 T，即独立测试用例的数量（1 ≤ T ≤ 10⁴）。

接下来有 T 组测试用例，每组包含 5 个整数 A、B、cA、cB、fA。

输出格式（输出到终端 / 标准输出）

每组测试用例的答案单独输出一行。

注意：本题中涉及的整数数值较大，可能需要使用 64 位整数数据类型（例如 C/C++ 中的 “long long”）。

（示例中的大整数）1000000000000000000

样例输入1

2
2 3 1 1 6
2 3 1 1 4

样例输出 1

1
0

样例输入 2

5
0 0 2 3 5
0 1 2 3 5
1 0 2 3 5
10 10 2 3 5
0 0 1 1000000000 1000000000

样例输出 2

9
8
7
0
1000000000000000000

示例说明

对于第一组测试用例，贝茜最初没有任何筹码。

若她额外获得 9 个筹码，无论这些筹码如何分配，都能通过操作最终拥有至少 5 个 A 型筹码。例如，若获得 2 个 A 型筹码和 7 个 B 型筹码，可执行 2 次兑换操作，最终得到 6 个 A 型筹码（6 ≥ 5）。

但如果她只额外获得 8 个 B 型筹码，则最多只能兑换得到 4 个 A 型筹码（4 ＜ 5），无法满足要求。

对于第四组测试用例，贝茜最初拥有的 A 型筹码数量就已满足要求。

评分标准

• 输入 3：cA = cB = 1
• 输入 4-5：所有用例的 x 值均不超过 10
• 输入 6-7：cA = 2，cB = 3
• 输入 8-12：无额外限制

补充说明

初始状态下有 A 个 A 型筹码、B 个 B 型筹码。允许执行无限次兑换操作：只要当前拥有的 B 型筹码数量≥cB，就能用 cB 个 B 型筹码兑换 cA 个 A 型筹码。

现在需要 “额外获得 x 个随机筹码”，“随机” 意味着：这 x 个筹码中 A 型和 B 型的数量比例是不可控制的（等价于考虑最坏情况下的筹码分配）。

题目要求找到最小的非负整数 x，使得：无论这 x 个筹码如何分配（A 型和 B 型各有多少个），都一定能通过若干次兑换操作，最终让 A 型筹码的数量≥fA。

贝茜还会得到一个参数 k，k 的取值为 0 或 1。设 M 为你所设计方案中的操作次数：

• 若 k=0，则 M 必须等于最小可能的操作次数；
• 若 k=1，则 M 最多可以比最小可能的操作次数多 1。

（输入格式补充）第一行包含 T（独立测试用例的数量，1 ≤ T ≤ 10⁴）和 k（0 ≤ k ≤ 1）。