Little Cyan Fish er nemandi við Powerful Kubic University (PKU). Árið 2023 tók Little Cyan Fish námskeiðið Inngangur að Kubic-fræðum sem prófessor Kubic kenndi. Eftir að hafa sannað setninguna um fjóra Kubic varð Little Cyan Fish aðstoðarkennari í þessu námskeiði. Í lokaprófi námskeiðsins útbjó Little Cyan Fish eftirfarandi áhugaverða litla dæmi:

• Gefin er frumtala $p$ og fjórar heiltölur $a_1, a_2, a_3, a_4$ á bilinu $1$ til $p - 1$.
• Leystu jöfnuna $a_1x_1 + a_2x_2 + a_3x_3 + a_4x_4 \equiv m \pmod p$, þar sem $x_i \ge 0$.

Þetta dæmi er of einfalt fyrir þig sem hefur tekið Inngang að Kubic-fræðum. Þess vegna gefur Little Cyan Fish þér fjórar heiltölur í viðbót, $b_1, b_2, b_3, b_4$. Little Cyan Fish vill að lausnin þín lágmarki gildið á $b_1x_1 + b_2x_2 + b_3x_3 + b_4x_4$ á sama tíma og hún uppfyllir jöfnuna hér að ofan.

Inntak

Það eru mörg prófunartilvik. Fyrsta línan í inntakinu inniheldur eina heiltölu $T$ ($1 \le T \le 10^4$), sem gefur til kynna fjölda prófunartilvika.

Fyrir hvert prófunartilvik inniheldur fyrsta línan í inntakinu tvær heiltölur $p$ og $m$ ($2 \le p \le 1.01 \times 10^9, 0 \le m < p$, tryggt er að $p$ sé frumtala).

Næsta lína inniheldur fjórar heiltölur $a_1, a_2, a_3, a_4$ ($1 \le a_1, a_2, a_3, a_4 < p$).

Næsta lína inniheldur fjórar heiltölur $b_1, b_2, b_3, b_4$ ($1 \le b_1, b_2, b_3, b_4 \le 10^9$).

Það er tryggt að summa $\lceil \sqrt{p} \rceil$ yfir öll prófunartilvik fari ekki yfir $2^{17}$.

Úttak

Fyrir hvert prófunartilvik skaltu prenta eina línu sem inniheldur eina heiltölu, sem gefur til kynna lágmarksgildið á $b_1x_1 + b_2x_2 + b_3x_3 + b_4x_4$.

Dæmi

Inntak 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

Úttak 1

199
76000000000
187