Little Cyan Fish est un étudiant à la Powerful Kubic University (PKU). En 2023, Little Cyan Fish a suivi le cours d'Introduction à la Théorie Kubique enseigné par le Prof. Kubic. Après avoir démontré le Théorème des Quatre Cubiques, Little Cyan Fish est devenu assistant d'enseignement pour ce cours. Lors de l'examen final, Little Cyan Fish a préparé le petit problème intéressant suivant :

• Étant donné un nombre premier $p$ et quatre entiers $a_1, a_2, a_3, a_4$ compris entre $1$ et $p - 1$.
• Résoudre l'équation $a_1x_1 + a_2x_2 + a_3x_3 + a_4x_4 \equiv m \pmod{p}$, où $x_i \ge 0$.

Ce problème est trop simple pour vous, qui avez suivi l'Introduction à la Théorie Kubique. Par conséquent, Little Cyan Fish vous donne quatre autres entiers $b_1, b_2, b_3, b_4$. Little Cyan Fish souhaite que vous trouviez une solution minimisant la valeur de $b_1x_1 + b_2x_2 + b_3x_3 + b_4x_4$ tout en satisfaisant l'équation ci-dessus.

Entrée

Il y a plusieurs cas de test. La première ligne de l'entrée contient un entier unique $T$ ($1 \le T \le 10^4$), indiquant le nombre de cas de test.

Pour chaque cas de test, la première ligne contient deux entiers $p$ et $m$ ($2 \le p \le 1.01 \times 10^9$, $0 \le m < p$, il est garanti que $p$ est un nombre premier).

La ligne suivante contient quatre entiers $a_1, a_2, a_3, a_4$ ($1 \le a_1, a_2, a_3, a_4 < p$).

La ligne suivante contient quatre entiers $b_1, b_2, b_3, b_4$ ($1 \le b_1, b_2, b_3, b_4 \le 10^9$).

Il est garanti que la somme de $\sqrt{p}$ sur tous les cas de test n'excède pas $2^{17}$.

Sortie

Pour chaque cas de test, affichez une seule ligne contenant un entier, indiquant la valeur minimale de $b_1x_1 + b_2x_2 + b_3x_3 + b_4x_4$.

Exemples

Entrée 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

Sortie 1

199
76000000000
187