Little Cyan Fish 是強大立方大學 (PKU) 的一名學生。2023 年，Little Cyan Fish 修習了由 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$。

對於修過「立方理論導論」的你來說，這個問題太簡單了。因此，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