Міжнародний клуб гладження капібар готує футболки для заходу. Є чотири розміри: S, M, L та XL у порядку зростання. Необхідна кількість футболок кожного розміру становить $n_{\mathrm{S}}$, $n_{\mathrm{M}}$, $n_{\mathrm{L}}$ та $n_{\mathrm{XL}}$ відповідно. За стандартної насиченості кольору для футболок розмірів S, M, L та XL потрібно $B$, $Br$, $Br^2$ та $Br^3$ одиниць барвника відповідно.

Фарбувальна машина використовує цілочисельну насиченість $x$. Мінімальна дозволена насиченість кольору дорівнює $P$, а $x = K$ є стандартною насиченістю. Отже, $x$ має задовольняти умову $P \le x \le K$. Якщо за стандартної насиченості для футболки потрібно $q$ одиниць барвника, то її фарбування за насиченості $x$ витрачає $\lceil qx/K \rceil$ одиниць. Усі футболки мають фарбуватися з однаковою насиченістю $x$.

Маючи $A$ одиниць барвника, знайдіть максимально можливу насиченість $x$, за якої можна пофарбувати всі футболки, витративши не більше ніж $A$ одиниць барвника. Якщо такого $x$ не існує, виведіть $-1$.

Вхідні дані

Вхідні дані містять $T$ тестових випадків. Перший рядок містить ціле число $T$ ($1 \le T \le 100$) — кількість тестових випадків. Кожен тестовий випадок складається з дев'яти цілих чисел, заданих у такому форматі:

$$ 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}}$ та $n_{\mathrm{XL}}$ позначають кількість футболок розмірів S, M, L та XL відповідно ($0 \le n_{\mathrm{S}}, n_{\mathrm{M}}, n_{\mathrm{L}}, n_{\mathrm{XL}} \le 10^5$ і $n_{\mathrm{S}} + n_{\mathrm{M}} + n_{\mathrm{L}} + n_{\mathrm{XL}} \ge 1$).

Величина $r$ позначає коефіцієнт, у який збільшується кількість барвника, необхідна за стандартної насиченості, з кожним збільшенням розміру ($1 \le r \le 10$).

$A$ позначає загальну доступну кількість барвника в одиницях ($0 \le A \le 10^{15}$).

$B$ позначає кількість барвника в одиницях, необхідну для фарбування однієї футболки розміру S за стандартної насиченості ($1 \le B \le 10^6$).

$P$ позначає мінімальну дозволену насиченість кольору, а $K$ позначає стандартну насиченість кольору ($1 \le P \le K \le 10^9$).

Вихідні дані

Для кожного тестового випадку виведіть максимальне ціле число $x$, таке що $P \le x \le K$ і всі футболки можна пофарбувати, використавши щонайбільше $A$ одиниць барвника. Якщо такого цілого числа не існує, виведіть $-1$.

Приклади

Вхідні дані 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

Вихідні дані 1

6
-1
999999