Международный клуб поглаживания капибар готовит футболки для мероприятия. Существует четыре размера: 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