题目描述

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\)。

现在还会额外给 Bessie \(x\) 枚随机芯片。这里的“随机”表示这 \(x\) 枚芯片中每一枚都可能是 A 型或 B 型，因此你无法控制它们的具体分配方式。

请你求出最小的非负整数 \(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
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

输出

9
8
7
0
1000000000000000000

说明

对于第二组样例中的第 1 个测试，Bessie 一开始没有任何芯片。如果额外给她任意 \(9\) 枚芯片，那么无论这些芯片如何分配，她都能最终得到至少 \(5\) 枚 A 型芯片。

例如，如果这 \(9\) 枚芯片中有 \(2\) 枚是 A 型、\(7\) 枚是 B 型，那么她可以兑换两次，最终得到 \(6 \ge 5\) 枚 A 型芯片。

但是如果只额外给她 \(8\) 枚芯片且全是 B 型芯片，那么她最多只能得到 \(4 < 5\) 枚 A 型芯片，因此 \(8\) 不够。

对于第 4 个测试，Bessie 一开始就已经拥有足够多的 A 型芯片，所以答案为 \(0\)。

数据范围

• 输入 3：\(c_A = c_B = 1\)
• 输入 4-5：所有测试满足答案 \(x \le 10\)
• 输入 6-7：\(c_A = 2, c_B = 3\)
• 输入 8-12：无额外限制

命题信息

原题命题：Benjamin Qi