Little Cyan Fish jest studentem na Powerful Kubic University (PKU). W 2023 roku Little Cyan Fish wziął udział w kursie Wprowadzenie do Teorii Kubicznej, prowadzonym przez prof. Kubica. Po udowodnieniu Twierdzenia Czterech Kubików, Little Cyan Fish został asystentem na tym kursie. Na egzaminie końcowym przygotował następujący interesujący problem:

• Dane są liczba pierwsza $p$ oraz cztery liczby całkowite $a_1, a_2, a_3, a_4$ z przedziału od $1$ do $p - 1$.
• Rozwiąż równanie $a_1x_1 + a_2x_2 + a_3x_3 + a_4x_4 \equiv m \pmod{p}$, gdzie $x_i \ge 0$.

Ten problem jest zbyt prosty dla kogoś, kto ukończył Wprowadzenie do Teorii Kubicznej. Dlatego Little Cyan Fish podaje dodatkowo cztery liczby całkowite $b_1, b_2, b_3, b_4$. Little Cyan Fish chce, abyś znalazł rozwiązanie minimalizujące wartość $b_1x_1 + b_2x_2 + b_3x_3 + b_4x_4$ przy zachowaniu powyższego równania.

Wejście

Dostępnych jest wiele zestawów danych. Pierwsza linia wejścia zawiera pojedynczą liczbę całkowitą $T$ ($1 \le T \le 10^4$), określającą liczbę zestawów danych.

Dla każdego zestawu danych, pierwsza linia zawiera dwie liczby całkowite $p$ oraz $m$ ($2 \le p \le 1.01 \times 10^9$, $0 \le m < p$, przy czym $p$ jest liczbą pierwszą).

Następna linia zawiera cztery liczby całkowite $a_1, a_2, a_3, a_4$ ($1 \le a_1, a_2, a_3, a_4 < p$).

Następna linia zawiera cztery liczby całkowite $b_1, b_2, b_3, b_4$ ($1 \le b_1, b_2, b_3, b_4 \le 10^9$).

Gwarantuje się, że suma $\sqrt{p}$ dla wszystkich zestawów danych nie przekracza $2^{17}$.

Wyjście

Dla każdego zestawu danych wypisz w pojedynczej linii jedną liczbę całkowitą, oznaczającą minimalną wartość $b_1x_1 + b_2x_2 + b_3x_3 + b_4x_4$.

Przykład

Wejście 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

Wyjście 1

199
76000000000
187