问题 1. 芯片交换 (Chip Exchange)

USACO 2026 第一次竞赛，Bronze 组

奶牛 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$）。

输入格式 (输入从终端/stdin 读取):

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

随后是 $T$ 个测试用例，每个测试用例包含五个整数 $A,B,c_A,c_B,f_A$。

输出格式 (输出到终端/stdout):

将每个测试用例的答案打印在新的一行上。

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

示例输入：

2
2 3 1 1 6
2 3 1 1 4

示例输出：

1
0

示例输入：

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

示例输出：

9
8
7
0
1000000000000000000

问题出处：Benjamin Qi