Problem Description

The International Capybara Petting Club is preparing T-shirts for an event. There are four sizes, S, M, L, and XL, in increasing order. The numbers of T-shirts needed are $n_{\mathrm{S}},n_{\mathrm{M}},n_{\mathrm{L}}$, and $n_{\mathrm{XL}}$, respectively. At the standard color intensity, T-shirts of sizes S, M, L, and XL require $B,Br,Br^2$, and $Br^3$ units of dye, respectively.

The dyeing machine uses an integer intensity $x$. The minimum allowed color intensity is $P$, and $x=K$ is the standard intensity. Thus, $x$ must satisfy $P\le x\le K$. If a T-shirt requires $q$ units at the standard intensity, dyeing it at intensity $x$ uses $\lceil qx/K\rceil$ units. All T-shirts must use the same intensity $x$.

Given $A$ units of dye, find the maximum possible intensity $x$ such that all T-shirts can be dyed without using more than $A$ units. If no such $x$ exists, output -1.

Input Format

The input contains $T$ test cases. The first line contains an integer $T$ ($1\le T\le 100$), the number of test cases. Each test case consists of nine integers given in the following format:

n_S n_M n_L n_XL r A B P K

$n_{\mathrm{S}},n_{\mathrm{M}},n_{\mathrm{L}}$, and $n_{\mathrm{XL}}$ denote the numbers of T-shirts of sizes S, M, L, and XL, respectively ($0\le n_{\mathrm{S}},n_{\mathrm{M}},n_{\mathrm{L}},n_{\mathrm{XL}}\le 10^5$ and $n_{\mathrm{S}}+n_{\mathrm{M}}+n_{\mathrm{L}}+n_{\mathrm{XL}}\ge 1$).

The value $r$ denotes the factor by which the amount of dye required at the standard intensity increases with each increase in size ($1\le r\le 10$).

$A$ denotes the total amount of dye available, in units ($0\le A\le 10^{15}$).

$B$ denotes the amount of dye required to dye one size-S T-shirt at the standard intensity, in units ($1\le B\le 10^6$).

$P$ denotes the minimum allowed color intensity, and $K$ denotes the standard color intensity ($1\le P\le K\le 10^9$).

Output Format

For each test case, output the maximum integer $x$ such that $P\le x\le K$ and all T-shirts can be dyed using at most $A$ units of dye. If no such integer exists, output -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

6
-1
999999