Le Club international de caresses de capybaras prépare des t-shirts pour un événement. Il existe quatre tailles, S, M, L et XL, par ordre croissant. Les nombres de t-shirts nécessaires sont respectivement $n_{\mathrm{S}}$, $n_{\mathrm{M}}$, $n_{\mathrm{L}}$ et $n_{\mathrm{XL}}$. À l'intensité de couleur standard, les t-shirts de tailles S, M, L et XL nécessitent respectivement $B$, $Br$, $Br^2$ et $Br^3$ unités de teinture.

La machine à teindre utilise une intensité entière $x$. L'intensité de couleur minimale autorisée est $P$, et $x = K$ est l'intensité standard. Ainsi, $x$ doit vérifier $P \le x \le K$. Si un t-shirt nécessite $q$ unités à l'intensité standard, le teindre à l'intensité $x$ utilise $\lceil qx/K \rceil$ unités. Tous les t-shirts doivent utiliser la même intensité $x$.

Étant donné $A$ unités de teinture, trouvez l'intensité maximale possible $x$ telle que tous les t-shirts puissent être teints sans utiliser plus de $A$ unités. S'il n'existe aucun tel $x$, affichez $-1$.

Entrée

L'entrée contient $T$ cas de test. La première ligne contient un entier $T$ ($1 \le T \le 100$), le nombre de cas de test. Chaque cas de test consiste en neuf entiers donnés dans le format suivant :

$$ 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}}$ et $n_{\mathrm{XL}}$ désignent respectivement les nombres de t-shirts de tailles S, M, L et XL ($0 \le n_{\mathrm{S}}, n_{\mathrm{M}}, n_{\mathrm{L}}, n_{\mathrm{XL}} \le 10^5$ et $n_{\mathrm{S}} + n_{\mathrm{M}} + n_{\mathrm{L}} + n_{\mathrm{XL}} \ge 1$).

La valeur $r$ désigne le facteur par lequel la quantité de teinture requise à l'intensité standard augmente à chaque passage à la taille supérieure ($1 \le r \le 10$).

$A$ désigne la quantité totale de teinture disponible, en unités ($0 \le A \le 10^{15}$).

$B$ désigne la quantité de teinture requise pour teindre un t-shirt de taille S à l'intensité standard, en unités ($1 \le B \le 10^6$).

$P$ désigne l'intensité de couleur minimale autorisée, et $K$ désigne l'intensité de couleur standard ($1 \le P \le K \le 10^9$).

Sortie

Pour chaque cas de test, affichez le plus grand entier $x$ tel que $P \le x \le K$ et que tous les t-shirts puissent être teints en utilisant au plus $A$ unités de teinture. S'il n'existe aucun tel entier, affichez $-1$.

Exemples

Entrée 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

Sortie 1

6
-1
999999