Little Cyan Fish is a student studying at the Powerful Kubic University (PKU). In 2023, Little Cyan Fish took the course Introduction to the Kubic Theory taught by Prof. Kubic. After proving the Four Kubic Theorem, Little Cyan Fish became a teaching assistant for this course. In the final exam of this course, Little Cyan Fish prepared the following interesting little problem:

• Given a prime $p$ and four integers $a_1, a_2, a_3, a_4$ between $1$ and $p - 1$.
• Solve the equation $a_1x_1 + a_2x_2 + a_3x_3 + a_4x_4 \equiv m \pmod p$, where $x_i \ge 0$.

This problem is too simple for you, who have taken Introduction to the Kubic Theory. Therefore, Little Cyan Fish gives you another four integers $b_1, b_2, b_3, b_4$. Little Cyan Fish wants your solution to minimize the value of $b_1x_1 + b_2x_2 + b_3x_3 + b_4x_4$ while satisfying the above equation.

Input

There are multiple test cases. The first line of the input contains a single integer $T$ ($1 \le T \le 10^4$), indicating the number of test cases.

For each test case, the first line of the input contains two integers $p$ and $m$ ($2 \le p \le 1.01 \times 10^9$, $0 \le m < p$, guaranteed that $p$ is a prime).

The next line contains four integers $a_1, a_2, a_3, a_4$ ($1 \le a_1, a_2, a_3, a_4 < p$).

The next line contains four integers $b_1, b_2, b_3, b_4$ ($1 \le b_1, b_2, b_3, b_4 \le 10^9$).

It is guaranteed that the sum of $\sqrt{p}$ over all test cases does not exceed $2^{17}$.

Output

For each test case, output a single line containing one integer, indicating the minimum value of $b_1x_1 + b_2x_2 + b_3x_3 + b_4x_4$.

Examples

Input 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

Output 1

199
76000000000
187