Little Cyan Fish — Powerful Kubic University (PKU) университетінде оқитын студент. 2023 жылы Little Cyan Fish профессор Kubic жүргізген «Kubic теориясына кіріспе» курсын оқыды. Төрт Кубик теоремасын дәлелдегеннен кейін, Little Cyan Fish осы курстың оқытушы ассистенті болды. Осы курстың қорытынды емтиханында Little Cyan Fish келесі қызықты кішкентай есепті дайындады:

• Жай сан $p$ және $1$ мен $p - 1$ аралығындағы төрт бүтін сан $a_1, a_2, a_3, a_4$ берілген.
• $a_1x_1 + a_2x_2 + a_3x_3 + a_4x_4 \equiv m \pmod p$ теңдеуін шешіңіз, мұндағы $x_i \ge 0$.

«Kubic теориясына кіріспе» курсын оқыған сіз үшін бұл есеп тым оңай. Сондықтан Little Cyan Fish сізге тағы төрт бүтін сан $b_1, b_2, b_3, b_4$ береді. Little Cyan Fish сіздің шешіміңіз жоғарыдағы теңдеуді қанағаттандыра отырып, $b_1x_1 + b_2x_2 + b_3x_3 + b_4x_4$ мәнін барынша азайтқанын қалайды.

Кіріс деректер

Бірнеше тест жағдайлары бар. Кіріс деректердің бірінші қатарында тест жағдайларының санын білдіретін бір бүтін сан $T$ ($1 \le T \le 10^4$) берілген.

Әрбір тест жағдайы үшін бірінші қатарда екі бүтін сан $p$ және $m$ ($2 \le p \le 1.01 \times 10^9, 0 \le m < p$, $p$ жай сан екеніне кепілдік беріледі) берілген.

Келесі қатарда төрт бүтін сан $a_1, a_2, a_3, a_4$ ($1 \le a_1, a_2, a_3, a_4 < p$) берілген.

Келесі қатарда төрт бүтін сан $b_1, b_2, b_3, b_4$ ($1 \le b_1, b_2, b_3, b_4 \le 10^9$) берілген.

Барлық тест жағдайлары бойынша $\lceil \sqrt{p} \rceil$ қосындысы $2^{17}$-нен аспайтынына кепілдік беріледі.

Шығыс деректер

Әрбір тест жағдайы үшін $b_1x_1 + b_2x_2 + b_3x_3 + b_4x_4$ өрнегінің ең кіші мәнін білдіретін бір бүтін саннан тұратын бір қатар шығарыңыз.

Мысал

Кіріс деректер 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

Шығыс деректер 1

199
76000000000
187