Chip Exchange
Bessie the cow has in her possession A chips of type A and B chips of type B (0≤A,B≤109). She can perform the following operation as many times as she likes:
- If you have at least cB chips of type B, exchange cB chips of type B for cA chips of type A (1≤cA,cB≤109).
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 fA chips of type A (0≤fA≤109).
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.
SCORING:
- Input 3: cA=cB=1
- Inputs 4-5: x≤10 for all cases
- Inputs 6-7: cA=2, cB=3
- Inputs 8-12: No additional constraints.
Problem credits: Benjamin Qi
Source: USA Computing Olympiad.
Input Format
The first line contains T, the number of independent test cases (1≤T≤104).
Then follow T tests, each consisting of five integers A,B,cA,cB,fA.
Output Format
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++).