Little Cyan Fish ist ein Student an der Powerful Kubic University (PKU). Im Jahr 2023 belegte Little Cyan Fish den von Prof. Kubic unterrichteten Kurs „Einführung in die Kubic-Theorie“. Nachdem er den Vier-Kubic-Satz bewiesen hatte, wurde Little Cyan Fish Übungsleiter für diesen Kurs. Für die Abschlussprüfung dieses Kurses hat Little Cyan Fish das folgende interessante kleine Problem vorbereitet:

• Gegeben seien eine Primzahl $p$ und vier ganze Zahlen $a_1, a_2, a_3, a_4$ zwischen $1$ und $p - 1$.
• Löse die Gleichung $a_1x_1 + a_2x_2 + a_3x_3 + a_4x_4 \equiv m \pmod p$, wobei $x_i \ge 0$ gilt.

Dieses Problem ist zu einfach für dich, da du „Einführung in die Kubic-Theorie“ belegt hast. Daher gibt dir Little Cyan Fish vier weitere ganze Zahlen $b_1, b_2, b_3, b_4$. Little Cyan Fish möchte, dass deine Lösung den Wert von $b_1x_1 + b_2x_2 + b_3x_3 + b_4x_4$ minimiert und gleichzeitig die obige Gleichung erfüllt.

Eingabe

Es gibt mehrere Testfälle. Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl $T$ ($1 \le T \le 10^4$), die die Anzahl der Testfälle angibt.

Für jeden Testfall enthält die erste Zeile der Eingabe zwei ganze Zahlen $p$ und $m$ ($2 \le p \le 1.01 \times 10^9, 0 \le m < p$, wobei garantiert wird, dass $p$ eine Primzahl ist).

Die nächste Zeile enthält vier ganze Zahlen $a_1, a_2, a_3, a_4$ ($1 \le a_1, a_2, a_3, a_4 < p$).

Die nächste Zeile enthält vier ganze Zahlen $b_1, b_2, b_3, b_4$ ($1 \le b_1, b_2, b_3, b_4 \le 10^9$).

Es wird garantiert, dass die Summe von $\lceil \sqrt{p} \rceil$ über alle Testfälle $2^{17}$ nicht überschreitet.

Ausgabe

Gib für jeden Testfall eine einzelne Zeile mit einer ganzen Zahl aus, die den minimalen Wert von $b_1x_1 + b_2x_2 + b_3x_3 + b_4x_4$ angibt.

Beispiel

Eingabe 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

Ausgabe 1

199
76000000000
187