题目描述

奶牛 Bessie 拥有 \(A\) 个 A 型芯片和 \(B\) 个 B 型芯片（\(0\le A,B\le 10^9\)）。她可以按意愿多次执行以下操作：

• 如果你至少有 \(c_B\) 个 B 型芯片，则可以用 \(c_B\) 个 B 型芯片交换 \(c_A\) 个 A 型芯片（\(1\le c_A,c_B\le 10^9\)）。

请你确定一个最小的非负整数 \(x\)，使得以下条件成立：在收到 \(x\) 个额外的随机芯片后，可以保证 Bessie 最终能够拥有至少 \(f_A\) 个 A 型芯片（\(0\le f_A\le 10^9\)）。

输入格式

第一行包含 \(T\)，表示独立测试用例的数量（\(1\le T\le 10^4\)）。

接下来是 \(T\) 个测试用例，每个用例由五个整数 \(A\)、\(B\)、\(c_A\)、\(c_B\)、\(f_A\) 组成。

输出格式

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

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

输入输出样例 #1

输入 #1

2
2 3 1 1 6
2 3 1 1 4

输出 #1

1
0

输入输出样例 #2

输入 #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

说明/提示

对于第一个测试用例，Bessie 最初没有任何芯片。如果她收到任意 \(9\) 个额外芯片，她可以通过执行操作最终拥有至少 \(5\) 个 A 型芯片。例如，如果她收到 \(2\) 个 A 型芯片和 \(7\) 个 B 型芯片，她可以执行两次操作，最终拥有 \(6 \ge 5\) 个 A 型芯片。然而，如果她只收到 \(8\) 个 B 型芯片，她最终只能拥有 \(4 < 5\) 个 A 型芯片。

对于第四个测试用例，她从一开始就拥有足够的 A 型芯片。

---

• 输入 \(3\)：\(c_A = c_B = 1\)
• 输入 \(4\)-\(5\)：所有情况下 \(x \le 10\)
• 输入 \(6\)-\(7\)：\(c_A = 2\)，\(c_B = 3\)
• 输入 \(8\)-\(12\)：无额外约束。