题目描述

奶牛贝西拥有 A枚 A 型芯片和 B枚 B 型芯片（0≤A,B≤10⁹）。她可以任意次数执行以下操作： 若至少有 c$_B$枚B 型芯片，可将 c$_B$枚B型芯片兑换为  c$_A$枚 A 型芯片（1≤c_A,c_B≤10⁹）。 请确定最小的非负整数 x，使得：在获得 x枚额外的任意芯片后，无论这些芯片是 A 型还是 B 型，贝西最终都能拥有至少 f$_A$枚A型芯片（0≤f$_A$≤10⁹）。

输入格式

第一行包含T,表示独立测试用例的数量（1≤T≤10⁴）。 随后是 T组测试数据，每组包含五个整数： A, B, c$_A$, c$_B$, f$_A$。

输出格式

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

样例输入1

123 500

样例输出1

623

样例输入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

样例解释

对于第一个测试用例，贝西初始没有任何芯片。如果她获得任意 9 枚额外芯片，就能通过操作最终得到至少 5 枚 A 型芯片。例如，若获得 2 枚 A 型芯片和 7 枚 B 型芯片，她可执行两次操作，最终得到 6 枚 A 型芯片（≥5）。但如果她只获得 8 枚 B 型芯片，最终只能得到 4 枚 A 型芯片（<5）。 对于第四个测试用例，她初始的 A 型芯片数量已足够。

数据限制

输入3：c$_A$ = c$_B$ = 1 输入4-5：所有测试用例中 x ≤ 10 输入6-7：c$_A$=2，c$_B$=3 输入8-12：无额外约束