國際摸水豚俱樂部正在為一場活動準備 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