국제 카피바라 쓰다듬기 클럽은 행사를 위해 티셔츠를 준비하고 있습니다. 티셔츠의 치수는 작은 것부터 순서대로 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$ 단위의 염료가 주어질 때, $A$ 단위 이하의 염료를 사용하여 모든 티셔츠를 염색할 수 있는 가능한 최대 농도 $x$를 구하세요. 그러한 $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$).

출력

각 테스트 케이스마다 $P \le x \le K$를 만족하고 최대 $A$ 단위의 염료를 사용하여 모든 티셔츠를 염색할 수 있는 가장 큰 정수 $x$를 출력하세요. 그러한 정수가 존재하지 않으면 $-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