Маленькая голубая рыбка — студент, обучающийся в Могучем Кубическом Университете (PKU). В 2023 году Маленькая голубая рыбка прослушала курс «Введение в кубическую теорию», который читал профессор Кубик. Доказав Четырехкубическую теорему, Маленькая голубая рыбка стала ассистентом преподавателя на этом курсе. На итоговом экзамене Маленькая голубая рыбка подготовила следующую интересную маленькую задачу:

• Дано простое число $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$.

Эта задача слишком проста для вас, тех, кто прослушал «Введение в кубическую теорию». Поэтому Маленькая голубая рыбка дает вам еще четыре целых числа $b_1, b_2, b_3, b_4$. Маленькая голубая рыбка хочет, чтобы вы нашли решение, минимизирующее значение $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$).

Гарантируется, что сумма $\sqrt{p}$ по всем тестовым случаям не превышает $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