马里奥在家里进行管道作业，以便将各种家用电器连接到供水系统。

有两种可用的水源插口类型：$\frac{1}{2}$ 和 $\frac{3}{4}$。一个类型为 $t$ 的初始插口已经连接到供水系统，但马里奥有 $a$ 个需要第一种类型插口的电器，以及 $b$ 个需要第二种类型插口的电器。

马里奥在工作中使用标准零件：

• 管路分流器允许将一个插口替换为多个相同类型的插口。对于这两种类型，都提供一分二和一分三的分流器。
• 管路适配器将任意类型的单个插口替换为另一种类型的插口。
• 管路堵头用于封闭任意单个插口。不同类型的插口使用不同类型的堵头。

每个零件在最近的五金店都有预设的价格。你可以假设每种零件都有无限个可用。

众所周知，马里奥是个非常吝啬的人，因此他希望你帮他确定，为了将他的电器连接到 $a$ 个第一种类型的插口和 $b$ 个第二种类型的插口，他需要花费的最少金额。任何插口都不能保持敞开且未使用，否则水会流出来。

输入格式

输入的第一行包含一个整数 $n$ — 你需要解决的测试用例数量（$1 \le n \le 50\,000$）。

接下来的 $n$ 行，每行包含十个整数：$a$，$b$，$cost_{\frac{1}{2} \times 2}$，$cost_{\frac{1}{2} \times 3}$，$cost_{\frac{3}{4} \times 2}$，$cost_{\frac{3}{4} \times 3}$，$cost_{\frac{1}{2} \times 0}$，$cost_{\frac{3}{4} \times 0}$，$cost_{\frac{1}{2} \leftrightarrow \frac{3}{4}}$，$t$。它们分别代表：需要 $\frac{1}{2}$ 和 $\frac{3}{4}$ 类型插口的家用电器数量，$\frac{1}{2}$ 类型一分二和一分三分流器的价格，$\frac{3}{4}$ 类型一分二和一分三分流器的价格，$\frac{1}{2}$ 和 $\frac{3}{4}$ 类型管路堵头的价格，$\frac{1}{2}$ 与 $\frac{3}{4}$ 类型之间的适配器价格，以及初始水源插口的类型（$1$ 表示 $\frac{1}{2}$ 类型，$2$ 表示 $\frac{3}{4}$ 类型）。

数字 $a$、$b$ 以及所有价格均为不超过 $10^9$ 的非负整数。

输出格式

对于每个测试用例，输出一行，包含一个整数 — 马里奥为了购买所有必要的工具，以将给定的水源插口连接到他的 $a$ 个 $\frac{1}{2}$ 类型家用电器和 $b$ 个 $\frac{3}{4}$ 类型家用电器，且不留下任何敞开和未使用的插口，所需要花费的最少金额。

样例

输入 1

3
1 1 1 1 1 1 1 1 1 1
2 3 5 6 3 1 2 1 1 2
0 3 10 10 5 8 6 4 3 1

输出 1

2
4
11

说明

在第一个样例中，你需要安装一个 $\frac{1}{2}$ 类型的分流器以连接两个设备，然后在其上连接一个从 $\frac{1}{2}$ 类型到 $\frac{3}{4}$ 类型的适配器。