Den internasjonale flodsvinklappeklubben forbereder T-skjorter til et arrangement. Det finnes fire størrelser, S, M, L og XL, i stigende rekkefølge. Antallet T-skjorter som trengs er henholdsvis $n_{\mathrm{S}}$, $n_{\mathrm{M}}$, $n_{\mathrm{L}}$ og $n_{\mathrm{XL}}$. Ved standard fargeintensitet krever T-skjorter i størrelsene S, M, L og XL henholdsvis $B$, $Br$, $Br^2$ og $Br^3$ enheter fargestoff.

Fargemaskinen bruker en heltallsintensitet $x$. Den laveste tillatte fargeintensiteten er $P$, og $x = K$ er standardintensiteten. Dermed må $x$ oppfylle $P \le x \le K$. Hvis en T-skjorte krever $q$ enheter ved standardintensiteten, vil farging ved intensitet $x$ bruke $\lceil qx/K \rceil$ enheter. Alle T-skjortene må bruke samme intensitet $x$.

Gitt $A$ enheter fargestoff, finn den maksimalt mulige intensiteten $x$ slik at alle T-skjortene kan farges uten å bruke mer enn $A$ enheter. Hvis det ikke finnes noen slik $x$, skriv ut $-1$.

Inndata

Inndataene inneholder $T$ testtilfeller. Den første linjen inneholder et heltall $T$ ($1 \le T \le 100$), antallet testtilfeller. Hvert testtilfelle består av ni heltall gitt på følgende format:

$$ 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}}$ og $n_{\mathrm{XL}}$ angir antallet T-skjorter i størrelsene henholdsvis S, M, L og XL ($0 \le n_{\mathrm{S}}, n_{\mathrm{M}}, n_{\mathrm{L}}, n_{\mathrm{XL}} \le 10^5$ og $n_{\mathrm{S}} + n_{\mathrm{M}} + n_{\mathrm{L}} + n_{\mathrm{XL}} \ge 1$).

Verdien $r$ angir faktoren som mengden fargestoff som kreves ved standardintensiteten øker med for hver økning i størrelse ($1 \le r \le 10$).

$A$ angir den totale mengden fargestoff som er tilgjengelig, i enheter ($0 \le A \le 10^{15}$).

$B$ angir mengden fargestoff som kreves for å farge én T-skjorte i størrelse S ved standardintensiteten, i enheter ($1 \le B \le 10^6$).

$P$ angir den laveste tillatte fargeintensiteten, og $K$ angir standard fargeintensitet ($1 \le P \le K \le 10^9$).

Utdata

For hvert testtilfelle, skriv ut det største heltallet $x$ slik at $P \le x \le K$ og alle T-skjortene kan farges ved å bruke høyst $A$ enheter fargestoff. Hvis det ikke finnes noe slikt heltall, skriv ut $-1$.

Eksempler

Inndata 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

Utdata 1

6
-1
999999