Prof. Pang 的口袋里只有 1 Au。（是的，Prof. Pang 来自 Austan，他在那里使用货币 Au。）

他将利用气球店和糖果店来赚钱：在气球店，Prof. Pang 可以用 1 Au 买 $k_{ab}$ 个气球，或者用 1 个糖果买 $k_{cb}$ 个气球。在糖果店，Prof. Pang 可以用 1 Au 买 $k_{ac}$ 个糖果，或者用 1 个气球买 $k_{bc}$ 个糖果。Prof. Pang 还可以卖掉一个气球获得 $k_{ba}$ Au，或者卖掉一个糖果获得 $k_{ca}$ Au。他面临的唯一限制是气球店只有 $n_b$ 个气球，糖果店只有 $n_c$ 个糖果。他只能在有库存时购买气球和糖果。即使他卖出了一些气球或糖果，商店里的气球和糖果数量也不会增加。

这六种交易中的每一种都可以按任意顺序执行任意次数（0 次或多次），但它们不可分割（例如，Prof. Pang 不能用 1/2 Au 买 $k_{ab}/2$ 个气球）。

请计算他最多能赚多少 Au。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 1000$)，表示测试用例的数量。

接下来的 $T$ 行中，每行包含八个整数 $n_b, n_c, k_{ab}, k_{ba}, k_{ac}, k_{ca}, k_{bc}, k_{cb}$ ($1 \le n_b, n_c \le 10^9$, $1 \le k_{ab}, k_{ba}, k_{ac}, k_{ca}, k_{bc}, k_{cb} \le 100$)，以空格分隔。

输出格式

对于每个测试用例，输出一行包含答案。

样例

样例输入 1

6
2 2 2 2 2 2 2 2
78 74 5 3 10 2 4 7
31 75 3 6 6 1 8 4
91 86 4 2 9 5 8 5
48 89 3 9 2 3 5 7
13 25 5 7 6 1 2 4

样例输出 1

7
355
239
571
637
109

说明

在第一个样例中，Prof. Pang 用 1 Au 买了 2 个气球，然后卖掉 2 个气球得到了 4 Au。接着他用 1 Au 买了 2 个糖果，卖掉 2 个糖果得到了 4 Au。