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

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_{\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}}$, 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

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$.

Example

Input 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

Output 1

6
-1
999999