Międzynarodowy Klub Głaskania Kapibar przygotowuje koszulki na wydarzenie. Dostępne są cztery rozmiary: S, M, L oraz XL, w kolejności rosnącej. Liczby potrzebnych koszulek wynoszą odpowiednio $n_{\mathrm{S}}$, $n_{\mathrm{M}}$, $n_{\mathrm{L}}$ oraz $n_{\mathrm{XL}}$. Przy standardowej intensywności koloru koszulki w rozmiarach S, M, L oraz XL wymagają odpowiednio $B$, $Br$, $Br^2$ oraz $Br^3$ jednostek barwnika.

Maszyna farbująca używa całkowitej intensywności $x$. Minimalna dozwolona intensywność koloru wynosi $P$, a $x = K$ jest intensywnością standardową. Zatem $x$ musi spełniać warunek $P \le x \le K$. Jeśli koszulka wymaga $q$ jednostek przy intensywności standardowej, zafarbowanie jej przy intensywności $x$ zużywa $\lceil qx/K \rceil$ jednostek. Wszystkie koszulki muszą zostać zafarbowane z tą samą intensywnością $x$.

Mając do dyspozycji $A$ jednostek barwnika, znajdź maksymalną możliwą intensywność $x$, przy której wszystkie koszulki można zafarbować, nie zużywając więcej niż $A$ jednostek. Jeśli takie $x$ nie istnieje, wypisz $-1$.

Wejście

Wejście zawiera $T$ przypadków testowych. Pierwszy wiersz zawiera liczbę całkowitą $T$ ($1 \le T \le 100$), oznaczającą liczbę przypadków testowych. Każdy przypadek testowy składa się z dziewięciu liczb całkowitych podanych w następującym formacie:

$$ 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}}$ oraz $n_{\mathrm{XL}}$ oznaczają odpowiednio liczby koszulek w rozmiarach S, M, L oraz XL ($0 \le n_{\mathrm{S}}, n_{\mathrm{M}}, n_{\mathrm{L}}, n_{\mathrm{XL}} \le 10^5$ oraz $n_{\mathrm{S}} + n_{\mathrm{M}} + n_{\mathrm{L}} + n_{\mathrm{XL}} \ge 1$).

Wartość $r$ oznacza współczynnik, o jaki wzrasta ilość barwnika wymagana przy standardowej intensywności wraz z każdym kolejnym większym rozmiarem ($1 \le r \le 10$).

$A$ oznacza całkowitą dostępną ilość barwnika w jednostkach ($0 \le A \le 10^{15}$).

$B$ oznacza ilość barwnika wymaganą do zafarbowania jednej koszulki w rozmiarze S przy standardowej intensywności, w jednostkach ($1 \le B \le 10^6$).

$P$ oznacza minimalną dozwoloną intensywność koloru, a $K$ oznacza standardową intensywność koloru ($1 \le P \le K \le 10^9$).

Wyjście

Dla każdego przypadku testowego wypisz maksymalną liczbę całkowitą $x$ taką, że $P \le x \le K$ i wszystkie koszulki można zafarbować przy użyciu co najwyżej $A$ jednostek barwnika. Jeśli taka liczba całkowita nie istnieje, wypisz $-1$.

Przykład

Wejście 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

Wyjście 1

6
-1
999999