题目描述

国际水豚抚摸俱乐部正在为一场活动准备 T 恤。T 恤共有四种尺码，从小到大依次为 S、M、L、XL，所需数量分别为 $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$ 组测试数据。第一行包含一个整数 $T$（$1\le T\le 100$），表示测试数据组数。每组测试数据包含九个整数，格式如下：

n_S n_M n_L n_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。

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

6
-1
999999