Little Cyan Fish es un estudiante en la Powerful Kubic University (PKU). En 2023, Little Cyan Fish tomó el curso de Introducción a la Teoría Kubic impartido por el Prof. Kubic. Tras demostrar el Teorema de los Cuatro Kubic, Little Cyan Fish se convirtió en asistente de docencia para este curso. En el examen final de la asignatura, Little Cyan Fish preparó el siguiente pequeño problema interesante:

• Dados un número primo $p$ y cuatro enteros $a_1, a_2, a_3, a_4$ entre $1$ y $p - 1$.
• Resuelve la ecuación $a_1x_1 + a_2x_2 + a_3x_3 + a_4x_4 \equiv m \pmod{p}$, donde $x_i \ge 0$.

Este problema es demasiado simple para ti, que has cursado Introducción a la Teoría Kubic. Por lo tanto, Little Cyan Fish te proporciona otros cuatro enteros $b_1, b_2, b_3, b_4$. Little Cyan Fish desea que tu solución minimice el valor de $b_1x_1 + b_2x_2 + b_3x_3 + b_4x_4$ mientras se satisface la ecuación anterior.

Entrada

Existen múltiples casos de prueba. La primera línea de la entrada contiene un único entero $T$ ($1 \le T \le 10^4$), que indica el número de casos de prueba.

Para cada caso de prueba, la primera línea contiene dos enteros $p$ y $m$ ($2 \le p \le 1.01 \times 10^9$, $0 \le m < p$, se garantiza que $p$ es un número primo).

La siguiente línea contiene cuatro enteros $a_1, a_2, a_3, a_4$ ($1 \le a_1, a_2, a_3, a_4 < p$).

La siguiente línea contiene cuatro enteros $b_1, b_2, b_3, b_4$ ($1 \le b_1, b_2, b_3, b_4 \le 10^9$).

Se garantiza que la suma de $\sqrt{p}$ sobre todos los casos de prueba no excede $2^{17}$.

Salida

Para cada caso de prueba, imprime una única línea que contenga un entero, indicando el valor mínimo de $b_1x_1 + b_2x_2 + b_3x_3 + b_4x_4$.

Ejemplos

Entrada 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

Salida 1

199
76000000000
187