Polycarp muốn nấu một món súp. Để làm điều đó, anh ta cần phải mua chính xác n lít nước.

Chỉ có hai loại chai nước trong cửa hàng gần đó - chai 1 lít và  chai 2 lít . Có vô số chai của hai loại này trong cửa hàng.

Chai loại đầu tiên có giá a và chai loại thứ hai chi phí b.

Polycarp muốn chi càng ít tiền càng tốt. Nhiệm vụ của bạn là tìm ra số tiền tối thiểu. Polycarp cần mua chính xác n lít nước ở cửa hàng 

Bạn cũng phải trả lời q truy vấn độc lập.

Dòng đầu tiên chứa một số nguyên q (1≤q≤500) - số lượng truy vấn.

Tiếp theo n dòng chứa các truy vấn. Các truy vấn thứ i được đưa ra dưới dạng ba số nguyên được phân tách bằng dấu khoảng trống ni, ai, bi.

In q số nguyên. Mỗi dòng chứa 1 số nguyên là số tiền tối thiểu Polycarp cần mua chính xác n lít nước ở cửa hàng.