Bessie có \(A\) chip loại A và \(B\) chip loại B (\(0\le A,B\le 10^9\)). Cô có thể thực hiện thao tác sau bao nhiêu lần tùy thích:

• Nếu có ít nhất \(c_B\) chip loại B, đổi \(c_B\) chip loại B lấy \(c_A\) chip loại A (\(1\le c_A,c_B\le 10^9\)).

Hãy xác định số nguyên không âm nhỏ nhất \(x\) thỏa mãn điều sau: sau khi nhận thêm \(x\) chip ngẫu nhiên, Bessie được đảm bảo có thể đạt được ít nhất \(f_A\) chip loại A (\(0\le f_A\le 10^9\)).

Dữ liệu vào

Dòng đầu tiên chứa \(T\), số lượng bộ test độc lập (\(1\le T\le 10^4\)).

Tiếp theo là \(T\) bộ test, mỗi bộ gồm năm số nguyên \(A,B,c_A,c_B,f_A\).

Dữ liệu ra

Với mỗi bộ test, in đáp án trên một dòng riêng.

Lưu ý: Do các số nguyên trong bài có thể rất lớn, bạn có thể cần sử dụng kiểu số nguyên 64 bit (ví dụ, long long trong C/C++).

Ví dụ

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

Phân nhóm

• Input 3: \(c_A=c_B=1\).
• Input 4–5: \(x\le 10\) với mọi bộ test.
• Input 6–7: \(c_A=2\), \(c_B=3\).
• Input 8–12: Không có ràng buộc bổ sung.

Nguồn

USACO 2026 Contest 1, Bronze, bài Chip Exchange. Tác giả: Benjamin Qi.
https://usaco.org/index.php?page=viewproblem2&cpid=1539