Description

庞教授的口袋里只有 $1$ 个奥币。（是的，庞教授来自奥斯坦，他在那里使用奥币。）

他将利用一个气球店和一个糖果店来赚钱：在气球店，庞教授可以用 $1$ 个奥币买 $k_{ab}$ 个气球，或者用 $1$ 个糖果买 $k_{cb}$ 个气球。在糖果店，庞教授可以用 $1$ 个奥币买 $k_{ac}$ 个糖果，或者用 $1$ 个气球买 $k_{bc}$ 个糖果。庞教授还可以卖掉一个气球，得到 $k_{ba}$ 个奥币。他可以卖掉一个糖果，得到 $k_{ca}$ 个奥币。他唯一的限制是气球店里只有 $n_b$ 个气球，糖果店里只有 $n_c$ 个糖果。他只能在供应充足时购买气球和糖果。即使他卖掉了一些气球或糖果，商店里的气球和糖果数量也不会增加。

这六种交易可以以任何顺序进行任意次数（$0$ 次或更多），但它们不可分割（例如，庞教授不能用 $1/2$ 个奥币买 $k_{ab}/2$ 个气球）。

请找出他最多能赚多少个奥币。

Input Format

第一行包含一个整数 $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$)，它们之间用空格分隔。

Output Format

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

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

7
355
239
571
637
109

Hint

在第一个例子中，庞教授用 $1$ 个奥币买了 $2$ 个气球，然后卖掉 $2$ 个气球，得到 $4$ 个奥币。接着他用 $1$ 个奥币买了 $2$ 个糖果，卖掉 $2$ 个糖果，得到 $4$ 个奥币。 （由 ChatGPT 4o 翻译）