國際摸水豚俱樂部正為一場活動準備 T 恤。T 恤一共有四種尺碼，由細到大依次為 S、M、L 同埋 XL。所需嘅各尺碼 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$ 單位嘅染料，請搵出最大可能嘅濃度 $x$，令到所有 T 恤都可以喺唔用超過 $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 嘅 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 \le r \le 10$）。

$A$ 代表可用染料嘅總量，以單位計（$0 \le A \le 10^{15}$）。

$B$ 代表喺標準濃度下染一件 S 碼 T 恤所需嘅染料量，以單位計（$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