Little Cyan Fish er en student som studerer ved Powerful Kubic University (PKU). I 2023 tok Little Cyan Fish kurset Introduksjon til Kubic-teorien, undervist av prof. Kubic. Etter å ha bevist Fire-Kubic-teoremet, ble Little Cyan Fish gruppelærer for dette kurset. Til avsluttende eksamen i dette kurset forberedte Little Cyan Fish følgende interessante lille problem:

• Gitt et primtall $p$ og fire heltall $a_1, a_2, a_3, a_4$ mellom $1$ og $p - 1$.
• Løs ligningen $a_1x_1 + a_2x_2 + a_3x_3 + a_4x_4 \equiv m \pmod p$, der $x_i \ge 0$.

Dette problemet er for enkelt for deg som har tatt Introduksjon til Kubic-teorien. Derfor gir Little Cyan Fish deg ytterligere fire heltall $b_1, b_2, b_3, b_4$. Little Cyan Fish ønsker at løsningen din skal minimere verdien av $b_1x_1 + b_2x_2 + b_3x_3 + b_4x_4$ samtidig som den tilfredsstiller ligningen ovenfor.

Inndata

Det er flere testtilfeller. Den første linjen av inndataene inneholder et enkelt heltall $T$ ($1 \le T \le 10^4$), som angir antallet testtilfeller.

For hvert testtilfelle inneholder den første linjen av inndataene to heltall $p$ og $m$ ($2 \le p \le 1.01 \times 10^9, 0 \le m < p$, det er garantert at $p$ er et primtall).

Den neste linjen inneholder fire heltall $a_1, a_2, a_3, a_4$ ($1 \le a_1, a_2, a_3, a_4 < p$).

Den neste linjen inneholder fire heltall $b_1, b_2, b_3, b_4$ ($1 \le b_1, b_2, b_3, b_4 \le 10^9$).

Det er garantert at summen av $\lceil \sqrt{p} \rceil$ over alle testtilfeller ikke overstiger $2^{17}$.

Utdata

For hvert testtilfelle, skriv ut én enkelt linje som inneholder ett heltall, som angir den minste verdien av $b_1x_1 + b_2x_2 + b_3x_3 + b_4x_4$.

Eksempel

Inndata 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