Il Club Internazionale di Coccole ai Capibara sta preparando delle magliette per un evento. Ci sono quattro taglie, S, M, L e XL, in ordine crescente. Il numero di magliette necessarie è rispettivamente $n_{\mathrm{S}}$, $n_{\mathrm{M}}$, $n_{\mathrm{L}}$ e $n_{\mathrm{XL}}$. All'intensità di colore standard, le magliette di taglia S, M, L e XL richiedono rispettivamente $B$, $Br$, $Br^2$ e $Br^3$ unità di tintura.

La macchina tintoria utilizza un'intensità intera $x$. L'intensità di colore minima consentita è $P$, e $x = K$ è l'intensità standard. Pertanto, $x$ deve soddisfare $P \le x \le K$. Se una maglietta richiede $q$ unità all'intensità standard, tingerla all'intensità $x$ consuma $\lceil qx/K \rceil$ unità. Tutte le magliette devono utilizzare la stessa intensità $x$.

Date $A$ unità di tintura, trova la massima intensità possibile $x$ tale che tutte le magliette possano essere tinte senza utilizzare più di $A$ unità. Se non esiste alcun $x$ di questo tipo, stampa $-1$.

Input

L'input contiene $T$ casi di test. La prima riga contiene un intero $T$ ($1 \le T \le 100$), il numero di casi di test. Ogni caso di test è composto da nove interi forniti nel seguente formato:

$$ 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}}$ e $n_{\mathrm{XL}}$ indicano rispettivamente il numero di magliette di taglia S, M, L e XL ($0 \le n_{\mathrm{S}}, n_{\mathrm{M}}, n_{\mathrm{L}}, n_{\mathrm{XL}} \le 10^5$ e $n_{\mathrm{S}} + n_{\mathrm{M}} + n_{\mathrm{L}} + n_{\mathrm{XL}} \ge 1$).

Il valore $r$ indica il fattore di cui aumenta la quantità di tintura richiesta all'intensità standard a ogni incremento di taglia ($1 \le r \le 10$).

$A$ indica la quantità totale di tintura disponibile, in unità ($0 \le A \le 10^{15}$).

$B$ indica la quantità di tintura richiesta per tingere una maglietta di taglia S all'intensità standard, in unità ($1 \le B \le 10^6$).

$P$ indica l'intensità di colore minima consentita, e $K$ indica l'intensità di colore standard ($1 \le P \le K \le 10^9$).

Output

Per ogni caso di test, stampa il massimo intero $x$ tale che $P \le x \le K$ e tutte le magliette possano essere tinte utilizzando al massimo $A$ unità di tintura. Se non esiste un tale intero, stampa $-1$.

Esempi

Input 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

Output 1

6
-1
999999