国際カピバラなでなでクラブは、イベントに向けて T シャツを準備しています。T シャツには小さい順に S、M、L、XL の 4 種類のサイズがあります。必要な T シャツの枚数はそれぞれ $n_{\mathrm{S}}$、$n_{\mathrm{M}}$、$n_{\mathrm{L}}$、$n_{\mathrm{XL}}$ です。標準の色濃度では、サイズ S、M、L、XL の T シャツはそれぞれ $B$、$Br$、$Br^2$、$Br^3$ 単位の染料を必要とします。

染色機は整数の濃度 $x$ を使用します。許容される最小の色濃度は $P$ であり、$x = K$ が標準の濃度です。したがって、$x$ は $P \le x \le K$ を満たす必要があります。ある T シャツが標準の濃度で $q$ 単位の染料を必要とする場合、それを濃度 $x$ で染めるには $\lceil qx/K \rceil$ 単位の染料を使用します。すべての T シャツは同じ濃度 $x$ を使用しなければなりません。

$A$ 単位の染料が与えられたとき、使用する染料が $A$ 単位以下ですべての T シャツを染めることができるような最大の濃度 $x$ を求めてください。そのような $x$ が存在しない場合は $-1$ を出力してください。

入力

入力は $T$ 個のテストケースを含みます。1 行目にはテストケースの個数を表す整数 $T$（$1 \le T \le 100$）が与えられます。各テストケースは以下の形式で与えられる 9 個の整数からなります。

$$ 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 の T シャツの枚数を表します（$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 段階大きくなるごとに標準の濃度で必要な染料の量が増加する倍率を表します（$1 \le r \le 10$）。

$A$ は利用可能な染料の総量を単位数で表します（$0 \le A \le 10^{15}$）。

$B$ は標準の濃度でサイズ S の T シャツを 1 枚染めるのに必要な染料の量を単位数で表します（$1 \le B \le 10^6$）。

$P$ は許容される最小の色濃度を表し、$K$ は標準の色濃度を表します（$1 \le P \le K \le 10^9$）。

出力

各テストケースについて、$P \le x \le K$ を満たし、高々 $A$ 単位の染料ですべての T シャツを染めることができる最大の整数 $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