Bessie hiện có ~A~ đồng xu loại A và ~B~ đồng xu loại B ~(0 \le A,B \le 10^9)~.

Bessie có thể thực hiện thao tác sau không giới hạn số lần:

• Nếu có ít nhất ~c_B~ đồng xu loại B, Bessie có thể đổi ~c_B~ đồng xu loại B lấy ~c_A~ đồng xu loại A ~(1 \le c_A,c_B \le 10^9)~.

Bessie sẽ nhận thêm ~x~ đồng xu ngẫu nhiên. Mỗi đồng xu nhận thêm có thể thuộc loại A hoặc loại B.

Yêu cầu: Tìm số nguyên không âm ~x~ nhỏ nhất sao cho bất kể số xu nhận thêm được phân chia giữa hai loại A và B như thế nào, Bessie luôn có thể thực hiện các thao tác đổi xu để cuối cùng sở hữu ít nhất ~f_A~ đồng xu loại A ~(0 \le f_A \le 10^9)~.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên ~T~ ~(1 \le T \le 10^4)~, là số bộ test.
• Mỗi bộ test gồm một dòng chứa năm số nguyên ~A, B, c_A, c_B, f_A~.

Dữ liệu ra

Với mỗi bộ test, in ra một số nguyên ~x~ nhỏ nhất thỏa mãn yêu cầu bài toán.

Lưu ý: Kết quả có thể rất lớn, cần sử dụng kiểu số nguyên 64-bit (long long trong C++).

Ví dụ 1

Input

2
2 3 1 1 6
2 3 1 1 4

Output

1
0

Ví dụ 2

Input

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

Output

9
8
7
0
1000000000000000000

Giải thích

Test 1 của ví dụ 2:

Ban đầu Bessie không có đồng xu nào.

• Nếu nhận thêm ~9~ đồng xu bất kỳ, Bessie luôn có thể đổi xu để sở hữu ít nhất ~5~ đồng xu loại A.
• Ví dụ, nếu nhận được ~2~ xu A và ~7~ xu B, Bessie có thể thực hiện ~2~ lần đổi, thu được ~6~ xu A.
• Tuy nhiên, nếu chỉ nhận thêm ~8~ xu B, Bessie chỉ có thể đổi được ~4~ xu A, không đạt yêu cầu.

Do đó, kết quả nhỏ nhất là ~x = 9~.

Test 4 của ví dụ 2:

Bessie đã có đủ số xu loại A cần thiết ngay từ đầu, nên không cần nhận thêm xu nào.

Kết quả là ~x = 0~.

Giới hạn

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