Câu lạc bộ Quốc tế Vuốt ve Chuột lang nước đang chuẩn bị áo phông cho một sự kiện. Có bốn cỡ áo là S, M, L và XL theo thứ tự tăng dần. Số lượng áo phông cần thiết lần lượt là $n_{\mathrm{S}}$, $n_{\mathrm{M}}$, $n_{\mathrm{L}}$ và $n_{\mathrm{XL}}$. Ở độ đậm màu tiêu chuẩn, áo phông các cỡ S, M, L và XL lần lượt cần $B$, $Br$, $Br^2$ và $Br^3$ đơn vị thuốc nhuộm.

Máy nhuộm sử dụng độ đậm nguyên $x$. Độ đậm màu tối thiểu cho phép là $P$, và $x = K$ là độ đậm tiêu chuẩn. Do đó, $x$ phải thỏa mãn $P \le x \le K$. Nếu một chiếc áo phông cần $q$ đơn vị ở độ đậm tiêu chuẩn, thì việc nhuộm nó ở độ đậm $x$ sẽ sử dụng $\lceil qx/K \rceil$ đơn vị. Tất cả áo phông phải sử dụng cùng một độ đậm $x$.

Cho $A$ đơn vị thuốc nhuộm, hãy tìm độ đậm $x$ lớn nhất có thể sao cho tất cả áo phông đều có thể được nhuộm mà không dùng quá $A$ đơn vị. Nếu không tồn tại $x$ như vậy, hãy in ra $-1$.

Dữ liệu vào

Dữ liệu vào gồm $T$ bộ test. Dòng đầu tiên chứa một số nguyên $T$ ($1 \le T \le 100$) là số lượng bộ test. Mỗi bộ test gồm chín số nguyên được cho theo định dạng sau:

$$ n_{\mathrm{S}} \ n_{\mathrm{M}} \ n_{\mathrm{L}} \ n_{\mathrm{XL}} \ r \ A \ B \ P \ K $$

$n_{\mathrm{S}}$, $n_{\mathrm{M}}$, $n_{\mathrm{L}}$ và $n_{\mathrm{XL}}$ lần lượt biểu thị số lượng áo phông các cỡ S, M, L và XL ($0 \le n_{\mathrm{S}}, n_{\mathrm{M}}, n_{\mathrm{L}}, n_{\mathrm{XL}} \le 10^5$ và $n_{\mathrm{S}} + n_{\mathrm{M}} + n_{\mathrm{L}} + n_{\mathrm{XL}} \ge 1$).

Giá trị $r$ biểu thị hệ số nhân mà lượng thuốc nhuộm cần thiết ở độ đậm tiêu chuẩn tăng lên sau mỗi lần tăng cỡ áo ($1 \le r \le 10$).

$A$ biểu thị tổng lượng thuốc nhuộm hiện có, tính theo đơn vị ($0 \le A \le 10^{15}$).

$B$ biểu thị lượng thuốc nhuộm cần thiết để nhuộm một chiếc áo phông cỡ S ở độ đậm tiêu chuẩn, tính theo đơn vị ($1 \le B \le 10^6$).

$P$ biểu thị độ đậm màu tối thiểu cho phép, và $K$ biểu thị độ đậm màu tiêu chuẩn ($1 \le P \le K \le 10^9$).

Dữ liệu ra

Với mỗi bộ test, hãy in ra số nguyên $x$ lớn nhất sao cho $P \le x \le K$ và tất cả áo phông đều có thể được nhuộm bằng cách sử dụng tối đa $A$ đơn vị thuốc nhuộm. Nếu không tồn tại số nguyên như vậy, hãy in ra $-1$.

Ví dụ

Dữ liệu vào 1

3
1 1 1 1 2 15 2 1 12
2 0 1 0 3 8 2 4 10
0 0 0 1 10 1000 1 900000 999999

Dữ liệu ra 1

6
-1
999999