Một năm lại sắp qua đi

Tết này biết sẽ làm gì được đây

Tết sắp đến Tichpx quyết định làm bánh Chưng và bánh Giầy để bán. Với số tiền ít ỏi Tichpx chỉ mua được n (đơn vị cân nặng) gạo nếp. Giả sử nhân làm bánh Chưng và bánh Giầy Tichpx đã được người nào đó tặng thỏa mái dùng.

1. Mỗi bánh Chưng thì tốn \(a\) đơn vị cân nặng gạo nếp và bán được \(b\) đơn vị tiền tệ

2. Mỗi bánh Giầy thì tốn \(c\) đơn vị cân nặng gạo nếp và bán được \(d\) đơn vị tiền tệ

Bạn hãy tư vấn xem Tichpx nên làm bánh từng loại với số lượng như thế nào để thu được nhiều tiền nhất

Input

Dòng đầu là số nguyên dương \(t\) là số bộ test \( (1 \leq t \leq 100)\)

Mối bộ test trên một dòng gồm n và 4 số nguyên dương \(a, b, c, d\) có giá trị không vượt quá \(10^6\)

Output

Tương ứng với mỗi trường hợp kiểm thử in ra từng kết quả trên từng dòng.

Ví dụ

Input

2
10 5 10 6 18
21 4 4 9 10

Output

20
22

Giải thích

• Ở test thứ nhất có 10 đơn vị cân nặng gạo nếp ta sản xuất 2 cái bánh Chưng thì bán được 20 tiền

• Ở test thứ hai có 21 đơn vị cân nặng gạo ta sản xuất 3 bánh Chưng và 1 bánh Giầy tốn \(3x4+9=21\) gạo bán được \(3x4+10=22\) tiền