Internationella kapybaraklappningsklubben förbereder T-shirts inför ett evenemang. Det finns fyra storlekar, S, M, L och XL, i stigande ordning. Antalet T-shirts som behövs är $n_{\mathrm{S}}$, $n_{\mathrm{M}}$, $n_{\mathrm{L}}$ respektive $n_{\mathrm{XL}}$. Vid standardfärgintensiteten kräver T-shirts i storlekarna S, M, L och XL $B$, $Br$, $Br^2$ respektive $Br^3$ enheter färgämne.

Färgningsmaskinen använder en heltalsintensitet $x$. Den lägsta tillåtna färgintensiteten är $P$, och $x = K$ är standardintensiteten. Alltså måste $x$ uppfylla $P \le x \le K$. Om en T-shirt kräver $q$ enheter vid standardintensiteten förbrukar färgning vid intensiteten $x$ exakt $\lceil qx/K \rceil$ enheter. Alla T-shirts måste använda samma intensitet $x$.

Givet $A$ enheter färgämne, hitta den största möjliga intensiteten $x$ sådan att alla T-shirts kan färgas utan att använda mer än $A$ enheter. Om inget sådant $x$ finns, skriv ut $-1$.

Indata

Indatan innehåller $T$ testfall. Den första raden innehåller ett heltal $T$ ($1 \le T \le 100$), antalet testfall. Varje testfall består av nio heltal som ges i följande 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}}$ och $n_{\mathrm{XL}}$ betecknar antalet T-shirts i storlekarna S, M, L respektive XL ($0 \le n_{\mathrm{S}}, n_{\mathrm{M}}, n_{\mathrm{L}}, n_{\mathrm{XL}} \le 10^5$ och $n_{\mathrm{S}} + n_{\mathrm{M}} + n_{\mathrm{L}} + n_{\mathrm{XL}} \ge 1$).

Värdet $r$ betecknar faktorn med vilken mängden färgämne som krävs vid standardintensiteten ökar för varje steg upp i storlek ($1 \le r \le 10$).

$A$ betecknar den totala mängden tillgängligt färgämne, i enheter ($0 \le A \le 10^{15}$).

$B$ betecknar mängden färgämne som krävs för att färga en T-shirt i storlek S vid standardintensiteten, i enheter ($1 \le B \le 10^6$).

$P$ betecknar den lägsta tillåtna färgintensiteten, och $K$ betecknar standardfärgintensiteten ($1 \le P \le K \le 10^9$).

Utdata

För varje testfall, skriv ut det största heltalet $x$ sådant att $P \le x \le K$ och alla T-shirts kan färgas med högst $A$ enheter färgämne. Om inget sådant heltal finns, skriv ut $-1$.

Exempel

Indata 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