Little Cyan Fish は、Powerful Kubic University (PKU) で学ぶ学生です。2023年、Little Cyan Fish は Prof. Kubic が教える「Kubic 理論入門」というコースを受講しました。「Four Kubic Theorem」を証明した後、Little Cyan Fish はこのコースのティーチングアシスタントになりました。このコースの期末試験において、Little Cyan Fish は次のような興味深い小問題を作成しました。

• 素数 $p$ と、$1$ から $p - 1$ の範囲にある $4$ つの整数 $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 はさらに $4$ つの整数 $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$) が含まれます。

各テストケースの最初の行には、2 つの整数 $p$ と $m$ ($2 \le p \le 1.01 \times 10^9$, $0 \le m < p$, $p$ は素数であることが保証される) が含まれます。

次の行には、4 つの整数 $a_1, a_2, a_3, a_4$ ($1 \le a_1, a_2, a_3, a_4 < p$) が含まれます。

次の行には、4 つの整数 $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 行で出力してください。

入出力例

入力 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