奶牛 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

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

说明

对于第二组样例的第一个测试用例，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：无额外限制。