Little Cyan Fish è uno studente presso la Powerful Kubic University (PKU). Nel 2023, Little Cyan Fish ha seguito il corso Introduzione alla Teoria di Kubic tenuto dal Prof. Kubic. Dopo aver dimostrato il Teorema dei quattro Kubic, Little Cyan Fish è diventato assistente alla didattica per questo corso. Nell'esame finale di questo corso, Little Cyan Fish ha preparato il seguente interessante piccolo problema:

• Dato un numero primo $p$ e quattro numeri interi $a_1, a_2, a_3, a_4$ compresi tra $1$ e $p - 1$.
• Risolvere l'equazione $a_1x_1 + a_2x_2 + a_3x_3 + a_4x_4 \equiv m \pmod p$, dove $x_i \ge 0$.

Questo problema è troppo semplice per te, che hai seguito Introduzione alla Teoria di Kubic. Pertanto, Little Cyan Fish ti dà altri quattro numeri interi $b_1, b_2, b_3, b_4$. Little Cyan Fish vuole che la tua soluzione minimizzi il valore di $b_1x_1 + b_2x_2 + b_3x_3 + b_4x_4$ soddisfacendo al contempo l'equazione precedente.

Input

Ci sono più casi di test. La prima riga dell'input contiene un singolo intero $T$ ($1 \le T \le 10^4$), che indica il numero di casi di test.

Per ogni caso di test, la prima riga dell'input contiene due interi $p$ e $m$ ($2 \le p \le 1.01 \times 10^9, 0 \le m < p$, con la garanzia che $p$ sia un numero primo).

La riga successiva contiene quattro interi $a_1, a_2, a_3, a_4$ ($1 \le a_1, a_2, a_3, a_4 < p$).

La riga successiva contiene quattro interi $b_1, b_2, b_3, b_4$ ($1 \le b_1, b_2, b_3, b_4 \le 10^9$).

È garantito che la somma di $\lceil \sqrt{p} \rceil$ su tutti i casi di test non supera $2^{17}$.

Output

Per ogni caso di test, stampa una singola riga contenente un intero, che indica il valore minimo di $b_1x_1 + b_2x_2 + b_3x_3 + b_4x_4$.

Esempio

Input 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

Output 1

199
76000000000
187