El Club Internacional de Caricias a Capibaras está preparando camisetas para un evento. Hay cuatro tallas, S, M, L y XL, en orden creciente. Las cantidades de camisetas necesarias son $n_{\mathrm{S}}$, $n_{\mathrm{M}}$, $n_{\mathrm{L}}$ y $n_{\mathrm{XL}}$, respectivamente. Con la intensidad de color estándar, las camisetas de las tallas S, M, L y XL requieren $B$, $Br$, $Br^2$ y $Br^3$ unidades de tinte, respectivamente.

La máquina de teñido utiliza una intensidad entera $x$. La intensidad de color mínima permitida es $P$, y $x = K$ es la intensidad estándar. Por lo tanto, $x$ debe satisfacer $P \le x \le K$. Si una camiseta requiere $q$ unidades con la intensidad estándar, teñirla con intensidad $x$ utiliza $\lceil qx/K \rceil$ unidades. Todas las camisetas deben usar la misma intensidad $x$.

Dadas $A$ unidades de tinte, encuentra la máxima intensidad posible $x$ tal que todas las camisetas puedan teñirse sin usar más de $A$ unidades. Si no existe tal $x$, imprime $-1$.

Entrada

La entrada contiene $T$ casos de prueba. La primera línea contiene un entero $T$ ($1 \le T \le 100$), el número de casos de prueba. Cada caso de prueba consta de nueve enteros dados en el siguiente formato:

$$ 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}}$ y $n_{\mathrm{XL}}$ denotan las cantidades de camisetas de las tallas S, M, L y XL, respectivamente ($0 \le n_{\mathrm{S}}, n_{\mathrm{M}}, n_{\mathrm{L}}, n_{\mathrm{XL}} \le 10^5$ y $n_{\mathrm{S}} + n_{\mathrm{M}} + n_{\mathrm{L}} + n_{\mathrm{XL}} \ge 1$).

El valor $r$ denota el factor por el cual aumenta la cantidad de tinte requerida con la intensidad estándar con cada incremento de talla ($1 \le r \le 10$).

$A$ denota la cantidad total de tinte disponible, en unidades ($0 \le A \le 10^{15}$).

$B$ denota la cantidad de tinte requerida para teñir una camiseta de talla S con la intensidad estándar, en unidades ($1 \le B \le 10^6$).

$P$ denota la intensidad de color mínima permitida, y $K$ denota la intensidad de color estándar ($1 \le P \le K \le 10^9$).

Salida

Para cada caso de prueba, imprime el máximo entero $x$ tal que $P \le x \le K$ y todas las camisetas puedan teñirse usando a lo sumo $A$ unidades de tinte. Si no existe tal entero, imprime $-1$.

Ejemplos

Entrada 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

Salida 1

6
-1
999999