Little Cyan Fish on opiskelija, joka opiskelee Powerful Kubic Universityssä (PKU). Vuonna 2023 Little Cyan Fish kävi prof. Kubicin opettaman kurssin Johdatus Kubic-teoriaan. Todistettuaan Neljän Kubicin lauseen Little Cyan Fishistä tuli tämän kurssinופetusassistentti. Tämän kurssin loppukokeeseen Little Cyan Fish laati seuraavan mielenkiintoisen pienen tehtävän:

• Annetaan alkuluku $p$ sekä neljä kokonaislukua $a_1, a_2, a_3, a_4$ väliltä $1$ – $p - 1$.
• Ratkaise yhtälö $a_1x_1 + a_2x_2 + a_3x_3 + a_4x_4 \equiv m \pmod p$, missä $x_i \ge 0$.

Tämä tehtävä on liian yksinkertainen sinulle, joka olet käynyt Johdatus Kubic-teoriaan -kurssin. Siksi Little Cyan Fish antaa sinulle vielä neljä kokonaislukua $b_1, b_2, b_3, b_4$. Little Cyan Fish haluaa, että ratkaisusi minimoi lausekkeen $b_1x_1 + b_2x_2 + b_3x_3 + b_4x_4$ arvon samalla kun se toteuttaa yllä olevan yhtälön.

Syöte

Syötteessä on useita testitapauksia. Syötteen ensimmäinen rivi sisältää yhden kokonaisluvun $T$ ($1 \le T \le 10^4$), joka ilmaisee testitapausten lukumäärän.

Jokaisessa testitapauksessa ensimmäinen rivi sisältää kaksi kokonaislukua $p$ ja $m$ ($2 \le p \le 1.01 \times 10^9, 0 \le m < p$, on taattu, että $p$ on alkuluku).

Seuraava rivi sisältää neljä kokonaislukua $a_1, a_2, a_3, a_4$ ($1 \le a_1, a_2, a_3, a_4 < p$).

Seuraava rivi sisältää neljä kokonaislukua $b_1, b_2, b_3, b_4$ ($1 \le b_1, b_2, b_3, b_4 \le 10^9$).

On taattu, että arvojen $\lceil \sqrt{p} \rceil$ summa yli kaikkien testitapausten ei ylitä arvoa $2^{17}$.

Tuloste

Tulosta jokaista testitapausta kohden yksi rivi, joka sisältää yhden kokonaisluvun: lausekkeen $b_1x_1 + b_2x_2 + b_3x_3 + b_4x_4$ pienimmän arvon.

Esimerkki

Syöte 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

Tuloste 1

199
76000000000
187