Der Internationale Capybara-Streichelklub bereitet T-Shirts für eine Veranstaltung vor. Es gibt vier Größen, S, M, L und XL, in aufsteigender Reihenfolge. Die Anzahl der benötigten T-Shirts beträgt jeweils $n_{\mathrm{S}}$, $n_{\mathrm{M}}$, $n_{\mathrm{L}}$ und $n_{\mathrm{XL}}$. Bei der Standardfarbintensität benötigen T-Shirts der Größen S, M, L und XL jeweils $B$, $Br$, $Br^2$ bzw. $Br^3$ Einheiten Farbstoff.

Die Färbemaschine verwendet eine ganzzahlige Intensität $x$. Die minimal zulässige Farbintensität ist $P$, und $x = K$ ist die Standardintensität. Somit muss $x$ die Bedingung $P \le x \le K$ erfüllen. Wenn ein T-Shirt bei der Standardintensität $q$ Einheiten benötigt, verbraucht das Färben bei Intensität $x$ genau $\lceil qx/K \rceil$ Einheiten. Alle T-Shirts müssen mit derselben Intensität $x$ gefärbt werden.

Gegeben sind $A$ Einheiten Farbstoff. Finde die maximal mögliche Intensität $x$, sodass alle T-Shirts gefärbt werden können, ohne mehr als $A$ Einheiten zu verbrauchen. Falls kein solches $x$ existiert, gib $-1$ aus.

Eingabe

Die Eingabe enthält $T$ Testfälle. Die erste Zeile enthält eine ganze Zahl $T$ ($1 \le T \le 100$), die Anzahl der Testfälle. Jeder Testfall besteht aus neun ganzen Zahlen im folgenden 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}}$ und $n_{\mathrm{XL}}$ bezeichnen jeweils die Anzahl der T-Shirts der Größen S, M, L und XL ($0 \le n_{\mathrm{S}}, n_{\mathrm{M}}, n_{\mathrm{L}}, n_{\mathrm{XL}} \le 10^5$ und $n_{\mathrm{S}} + n_{\mathrm{M}} + n_{\mathrm{L}} + n_{\mathrm{XL}} \ge 1$).

Der Wert $r$ bezeichnet den Faktor, um den sich die bei der Standardintensität benötigte Farbstoffmenge mit jeder nächstgrößeren Größe erhöht ($1 \le r \le 10$).

$A$ bezeichnet die insgesamt verfügbare Farbstoffmenge in Einheiten ($0 \le A \le 10^{15}$).

$B$ bezeichnet die Farbstoffmenge in Einheiten, die benötigt wird, um ein T-Shirt der Größe S bei der Standardintensität zu färben ($1 \le B \le 10^6$).

$P$ bezeichnet die minimal zulässige Farbintensität und $K$ bezeichnet die Standardfarbintensität ($1 \le P \le K \le 10^9$).

Ausgabe

Gib für jeden Testfall die größte ganze Zahl $x$ aus, sodass $P \le x \le K$ gilt und alle T-Shirts mit höchstens $A$ Einheiten Farbstoff gefärbt werden können. Falls keine solche ganze Zahl existiert, gib $-1$ aus.

Beispiele

Eingabe 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

Ausgabe 1

6
-1
999999