描述

Bessie 拥有 A 类芯片 A 个和 B 类芯片 B 个。她可以进行若干次如下操作：

现在，她将额外获得 $x$ 个随机芯片（每个芯片可以是 A 或 B 类），求最小的非负整数 $x$ ，使得无论这 $x$ 个芯片如何分配类型，Bessie 都能通过若干次上述操作，最终拥有至少 $f_A$ 个 A 类芯片。

输入输出格式

第一行包含一个整数 $T$ ，表示独立测试用例的数量。接下来 $T$ 行，每行包含五个整数： $A, B, c_A, c_B, f_A$ 。

对每个测试用例输出一行，表示满足条件的最小 $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