题目描述

奶牛 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$：无额外约束。