Một bộ đèn pha lê đẹp mắt đang được bày bán trên TikTok. Anh N (chủ nhân của giải thưởng 40 triệu đồng) đang dự tính mua nó để trang trí cho nhà hàng của mình.

Bộ đèn gồm \(a\) bóng đèn màu xanh và \(b\) bóng đèn màu đỏ. Giá của mỗi bóng đèn màu xanh là \(x\) và mỗi bóng đèn màu đỏ là \(y\). Để đổi một bóng đèn bất kì từ xanh sang đỏ hoặc ngược lại thì anh ta phải trả thêm \(c\) đồng cho chủ shop. N được dùng thao tác đổi bóng đèn vô số lần, hãy giúp anh ta tìm chi phí tối thiểu để mua được bộ đèn đó.

Input

• Dòng đầu tiên chứa số nguyên dương \(T\) là số bộ dữ liệu
• Tiếp theo gồm \(T\) dòng, tương ứng với \(T\) bộ dữ liệu. Mỗi dòng chứa các số nguyên dương \(a, b, x, y, c\).

Output

• Gồm một số nguyên duy nhất là số tiền tối thiểu cần để mua bộ đèn.

Scoring

• \(T \le 100\) với mọi testcase.
• Gọi \(n = a + b\):
  • Subtask \(1\) (\(50\%\) số điểm): \(n, x, y, c \le 10^3\).
  • Subtask \(2\) (\(50\%\) số điểm): \(n, x, y, c \le 10^5\).

Example

3
2 1 1 1 1
3 2 10 100 1
0 5 10 1 1

3
52
5