小青魚係 Powerful Kubic University (PKU) 嘅一名學生。喺 2023 年，小青魚修讀咗由 Prof. Kubic 任教嘅《Kubic 理論導論》課程。喺證明咗「四立方定理」之後，小青魚成為咗呢門課嘅助教。喺呢門課嘅期末考試入面，小青魚準備咗下面呢個有趣嘅小問題：

• 俾定一個質數 $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 理論導論》嘅你嚟講，呢個問題太簡單喇。因此，小青魚又俾咗你另外四個整數 $b_1, b_2, b_3, b_4$。小青魚希望你嘅解喺滿足上述方程嘅同時，最小化 $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$）。

保證所有測試數據入面 $\lceil \sqrt{p} \rceil$ 嘅總和唔超過 $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