Trong một tiết học Nhập môn Tài chính, thầy giáo của CaiWinDao thách đố cả lớp: với một lượng tiền đúng \(C\) đồng thì có thể mua về được tối đa bao nhiêu bộ bài? Biết rằng đơn giá của mỗi bộ bài ở ngoài cửa hàng là \(p\) đồng, và việc mua bán các bộ bài phải chịu đánh thuế hai lần: cứ mua mỗi \(n_1\) bộ bài thì ta phải chịu đúng \(t_1\) đồng tiền thuế giá trị gia tăng, cứ mua mỗi \(n_2\) bộ bài thì ta phải chịu đúng \(t_2\) đồng tiền thuế tiêu thụ đặc biệt. Ví dụ, nếu \(n_1=2\) và \(n_2=4\) thì khi muốn mua \(4\) bộ bài ta phải chịu tổng cộng \(2*t_1+t_2\) đồng tiền thuế.

Vì cách tính thuế quá chồng chéo và phức tạp nên CaiWinDao đành đầu hàng thầy giáo và nhờ đến sự trợ giúp của các bạn. Hãy giúp CaiWinDao tính xem có thể mua tối đa bao nhiêu bộ bài với \(C\) đồng nhé!

Input

Dòng đầu chứa số nguyên dương \(T\leq 10\) là số lượng câu hỏi.

\(T\) dòng sau, mỗi dòng chứa sáu số nguyên dương \(C\), \(p\), \(n_1\), \(n_2\), \(t_1\), và \(t_2\) thể một câu hỏi từ thầy giáo của CaiWinDao.

Dữ liệu luôn đảm bảo \(1\leq p, t_1, t_2\leq 100\), \(1\leq n_1 < n_2\leq 100\).

Output

Gồm \(T\) số nguyên in trên \(T\) dòng riêng biệt là kết quả cho câu hỏi tương ứng.

Ví dụ

Input

1
80 10 2 4 10 20

Output

4

Ràng buộc

• Subtask 1 (40 điểm): \(C \leq 10^6\).
• Subtask 2 (60 điểm): \(C \leq 10^{15}\).