Little Cyan Fish är en student som studerar vid Powerful Kubic University (PKU). År 2023 läste Little Cyan Fish kursen Introduktion till Kubic-teorin som undervisades av prof. Kubic. Efter att ha bevisat Fyra-Kubic-satsen blev Little Cyan Fish hjälplärare för denna kurs. Till slutprovet i kursen förberedde Little Cyan Fish följande intressanta lilla problem:

• Givet ett primtal $p$ och fyra heltal $a_1, a_2, a_3, a_4$ mellan $1$ och $p - 1$.
• Lös ekvationen $a_1x_1 + a_2x_2 + a_3x_3 + a_4x_4 \equiv m \pmod p$, där $x_i \ge 0$.

Detta problem är för enkelt för dig som har läst Introduktion till Kubic-teorin. Därför ger Little Cyan Fish dig ytterligare fyra heltal $b_1, b_2, b_3, b_4$. Little Cyan Fish vill att din lösning ska minimera värdet av $b_1x_1 + b_2x_2 + b_3x_3 + b_4x_4$ samtidigt som ovanstående ekvation uppfylls.

Indata

Det finns flera testfall. Den första raden i indata innehåller ett enda heltal $T$ ($1 \le T \le 10^4$), som anger antalet testfall.

För varje testfall innehåller den första raden i indata två heltal $p$ och $m$ ($2 \le p \le 1.01 \times 10^9, 0 \le m < p$, det garanteras att $p$ är ett primtal).

Nästa rad innehåller fyra heltal $a_1, a_2, a_3, a_4$ ($1 \le a_1, a_2, a_3, a_4 < p$).

Nästa rad innehåller fyra heltal $b_1, b_2, b_3, b_4$ ($1 \le b_1, b_2, b_3, b_4 \le 10^9$).

Det garanteras att summan av $\lceil \sqrt{p} \rceil$ över alla testfall inte överstiger $2^{17}$.

Utdata

För varje testfall, skriv ut en enda rad som innehåller ett heltal, vilket anger det minsta värdet av $b_1x_1 + b_2x_2 + b_3x_3 + b_4x_4$.

Exempel

Indata 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

Utdata 1

199
76000000000
187