Page not loading? Try clicking here.
Placeholder

#8840
Subtask

Chip Exchange 1s 1024MB

Problems

Bessie the cow has in her possession A chips of type A and B chips of type B (0≤A,B≤10^9). She can perform the following operation as many times as she likes:

  • If you have at least c_B chips of type B, exchange c_B chips of type B for c_A chips of type A (1≤c_A,c_B≤10^9).

Determine the minimum non-negative integer x such that the following holds: after receiving x additional random chips, it is guaranteed that Bessie can end up with at least f_A chips of type A (0≤f_A≤10^9).


Input

The first line contains T, the number of independent test cases (1≤T≤10^4).

Then follow T tests, each consisting of five integers A,B,c_A,c_B,f_A.


Output

Output the answer for each test on a separate line.

Note: The large size of integers involved in this problem may require the use of 64-bit integer data types (e.g., a "long long" in C/C++).


Subtask

# Score Condition
#110

c_A = c_B = 1

#220

x \le 10

#330

c_A =2, c_B = 3

#440

No additional constraints


Example #1

2
2 3 1 1 6
2 3 1 1 4
1
0

Example #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

For the first test, Bessie initially starts with no chips. If she receives any 9 additional chips, she can perform the operation to end up with at least 5 chips of type A. For example, if she receives 2 chips of type A and 7 chips of type B, she can perform the operation twice to end up with 6≥5 chips of type A. However, if she only receive 8 chips of type B, she can only end up with 4<5 chips of type A.

For the fourth test, she already has enough chips of type A from the start.



Source

USACO 2026 First Contest, Bronze

You must sign in to write code.