Klub Mengelus Kapibara Internasional sedang menyiapkan kaus untuk sebuah acara. Terdapat empat ukuran, yaitu S, M, L, dan XL, dalam urutan meningkat. Jumlah kaus yang dibutuhkan masing-masing adalah $n_{\mathrm{S}}$, $n_{\mathrm{M}}$, $n_{\mathrm{L}}$, dan $n_{\mathrm{XL}}$. Pada intensitas warna standar, kaus berukuran S, M, L, dan XL masing-masing membutuhkan $B$, $Br$, $Br^2$, dan $Br^3$ satuan pewarna.

Mesin pewarna menggunakan intensitas bilangan bulat $x$. Intensitas warna minimum yang diizinkan adalah $P$, dan $x = K$ adalah intensitas standar. Oleh karena itu, $x$ harus memenuhi $P \le x \le K$. Jika sebuah kaus membutuhkan $q$ satuan pada intensitas standar, mewarnainya pada intensitas $x$ akan menggunakan $\lceil qx/K \rceil$ satuan. Semua kaus harus menggunakan intensitas $x$ yang sama.

Diberikan $A$ satuan pewarna, carilah intensitas maksimum $x$ yang mungkin sehingga semua kaus dapat diwarnai tanpa menggunakan lebih dari $A$ satuan. Jika tidak ada $x$ yang memenuhi, keluarkan $-1$.

Masukan

Masukan terdiri atas $T$ kasus uji. Baris pertama berisi sebuah bilangan bulat $T$ ($1 \le T \le 100$), yaitu banyaknya kasus uji. Setiap kasus uji terdiri atas sembilan bilangan bulat yang diberikan dalam format berikut:

$$ 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}}$, dan $n_{\mathrm{XL}}$ masing-masing menyatakan jumlah kaus berukuran S, M, L, dan XL ($0 \le n_{\mathrm{S}}, n_{\mathrm{M}}, n_{\mathrm{L}}, n_{\mathrm{XL}} \le 10^5$ dan $n_{\mathrm{S}} + n_{\mathrm{M}} + n_{\mathrm{L}} + n_{\mathrm{XL}} \ge 1$).

Nilai $r$ menyatakan faktor pengali bertambahnya jumlah pewarna yang dibutuhkan pada intensitas standar setiap kali ukuran kaus meningkat ($1 \le r \le 10$).

$A$ menyatakan jumlah total pewarna yang tersedia, dalam satuan ($0 \le A \le 10^{15}$).

$B$ menyatakan jumlah pewarna yang dibutuhkan untuk mewarnai satu kaus ukuran S pada intensitas standar, dalam satuan ($1 \le B \le 10^6$).

$P$ menyatakan intensitas warna minimum yang diizinkan, dan $K$ menyatakan intensitas warna standar ($1 \le P \le K \le 10^9$).

Keluaran

Untuk setiap kasus uji, keluarkan bilangan bulat maksimum $x$ sedemikian sehingga $P \le x \le K$ dan semua kaus dapat diwarnai menggunakan paling banyak $A$ satuan pewarna. Jika tidak ada bilangan bulat seperti itu, keluarkan $-1$.

Contoh

Masukan 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

Keluaran 1

6
-1
999999