Trao Đổi Chip

Bessie có $A$ chip loại A và $B$ chip loại B. Cô có thể đổi $c_B$ chip loại B lấy $c_A$ chip loại A, thực hiện nhiều lần tùy ý.

Bessie muốn có ít nhất $f_A$ chip loại A. Để đạt được điều này, cô nhận thêm $x$ chip ngẫu nhiên (mỗi chip có thể là loại A hoặc B, do đối thủ chọn theo cách bất lợi nhất). Tìm giá trị nhỏ nhất của $x$ (không âm) sao cho bất kể $x$ chip thêm được phân phối thế nào, Bessie luôn đảm bảo đạt được ít nhất $f_A$ chip loại A (sau khi đổi tối ưu).

Dữ liệu vào

• Dòng 1: Số nguyên $T$ — số test case
• $T$ dòng tiếp theo, mỗi dòng chứa 5 số nguyên: $A$, $B$, $c_A$, $c_B$, $f_A$

Dữ liệu ra

Với mỗi test case, in ra một số nguyên — giá trị nhỏ nhất của $x$.

Ràng buộc

• $1\le T\le {10}^4$
• $0\le A,B\le {10}^9$
• $1\le c_A,c_B\le {10}^9$
• $0\le f_A\le {10}^9$
• Sử dụng kiểu dữ liệu 64-bit

Ví dụ