Little Cyan Fish — студент, який навчається в Powerful Kubic University (PKU). У 2023 році Little Cyan Fish прослухав курс «Вступ до теорії Kubic», який викладав проф. Kubic. Після доведення теореми про чотири кубіки Little Cyan Fish став асистентом викладача на цьому курсі. На фінальному іспиті з цього курсу Little Cyan Fish підготував таку цікаву невеличку задачу:

• Задано просте число $p$ та чотири цілі числа $a_1, a_2, a_3, a_4$ від $1$ до $p - 1$.
• Розв'яжіть рівняння $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