该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述：

王洋老师一觉醒来，发现自己竟然穿越到了当下最火的战术射击游戏《三角洲行动》中。冰冷的系统提示音在耳边响起："欢迎来到三角洲战场，完成以下四个核心任务，即可带着百万现金成功撤离。任务失败将永远滞留于此。" 深吸一口气，王洋老师握紧了手中的战术背包，开始了他的撤离之旅。

进入战场前，王洋老师需要在黑市进行最后的物资筹备。他目前拥有 A 元现金和 B 份基础物资。黑市商人提供了一项兑换服务：用 cB 份物资可以兑换 cA 元现金，这项服务可以无限次使用。

撤离的最低要求是最终至少拥有 fA 元现金。为了应对战场的不确定性，王洋老师可以携带 x 份备用物资进入战场。这些备用物资在落地后会随机变成现金或物资（每份独立随机，可能全是现金，也可能全是物资）。

请你帮助王洋老师计算最小的非负整数 x，使得无论这 x 份备用物资如何随机分配，他都一定能通过兑换凑够至少 fA 元现金，完成撤离的第一步要求。

输入格式：

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

接下来 T 行，每行包含五个整数 A, B, cA, cB, fA，含义如题目所述。

输出格式：

对于每个测试用例，输出一行一个整数，表示最小的 x 值。

注意：由于涉及的整数可能很大，建议使用 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