Little Cyan Fish 是 Powerful Kubic University (PKU) 的一名学生。2023 年，Little Cyan Fish 修读了由 Prof. Kubic 教授的《Kubic 理论导论》课程。在证明了“四立方定理”后，Little Cyan Fish 成为了该课程的助教。在这门课的期末考试中，Little Cyan Fish 准备了下面这个有趣的小问题：

• 给定一个素数 $p$ 和四个介于 $1$ 到 $p - 1$ 之间的整数 $a_1, a_2, a_3, a_4$。
• 求解方程 $a_1x_1 + a_2x_2 + a_3x_3 + a_4x_4 \equiv m \pmod p$，其中 $x_i \ge 0$。

对于已经修读过《Kubic 理论导论》的你来说，这个问题太简单了。因此，Little Cyan Fish 又给出了四个整数 $b_1, b_2, b_3, b_4$。Little Cyan Fish 希望你求出在满足上述方程的前提下，使得 $b_1x_1 + b_2x_2 + b_3x_3 + b_4x_4$ 的值最小的解。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$ ($1 \le T \le 10^4$)，表示测试数据的组数。

对于每组测试数据，第一行包含两个整数 $p$ 和 $m$ ($2 \le p \le 1.01 \times 10^9, 0 \le m < p$，保证 $p$ 是素数)。

下一行包含四个整数 $a_1, a_2, a_3, a_4$ ($1 \le a_1, a_2, a_3, a_4 < p$)。

下一行包含四个整数 $b_1, b_2, b_3, b_4$ ($1 \le b_1, b_2, b_3, b_4 \le 10^9$)。

保证所有测试数据的 $\sqrt{p}$ 之和不超过 $2^{17}$。

输出格式

对于每组测试数据，输出一行，包含一个整数，表示 $b_1x_1 + b_2x_2 + b_3x_3 + b_4x_4$ 的最小值。

样例

输入 1

3
101 99
1 2 3 4
5 6 7 8
998244353 114514
1919 811 123 777
1000000000 1000000000 1000000000 1000000000
1000000007 767336601
142205992 920557330 725753607 763861942
1 1 1 1

输出 1

199
76000000000
187