题目描述

嘉音有 $A$ 个原装母带和 $B$ 个加密母带。她可以进行若干次如下操作：

若此时至少有 $c_B$ 个加密母带，可以用 $c_B$ 个加密母带交换 $c_A$ 个原装母带。

请确定一个最小的非负整数 $x$，使得嘉音在收到 $x$ 个额外的随机母带（每一个都有可能是原装母带或者加密母带中的其中一个），最终通过交换嘉音能够至少有 $f_A$ 个原装母带。

格式要求

输入格式

第一行一个整数 $T$，表示测试数据数量 $(1 \leq T \leq 10^4)$。

接下来共 $T$ 组数据，每组数据一行五个整数 $A, B, c_A, c_B, f_A$。

输出格式

共 $T$ 行，每组数据输出一行一个整数 $x$。

样例

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

数据约束

对于 $10\%$ 的数据，$c_A = c_B = 1$。

对于另外 $20\%$ 的数据，$x \leq 10$。

对于另外 $20\%$ 的数据，$c_A = 2, c_B = 3$。

对于 $100\%$ 的数据，$0 \leq A \leq B \leq 10^9$，$1 \leq c_A, c_B \leq 10^9$，$0 \leq f_A \leq 10^9$，$1 \leq T \leq 10^4$。