国际水豚撸毛俱乐部正在为一场活动准备 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