Little Cyan Fish là một sinh viên đang theo học tại Đại học Kubic danh giá (PKU). Năm 2023, Little Cyan Fish tham gia khóa học Nhập môn Lý thuyết Kubic do Giáo sư Kubic giảng dạy. Sau khi chứng minh được Định lý Bốn Kubic, Little Cyan Fish trở thành trợ giảng cho khóa học này. Trong kỳ thi cuối kỳ, Little Cyan Fish đã chuẩn bị một bài toán nhỏ thú vị như sau:

• Cho một số nguyên tố $p$ và bốn số nguyên $a_1, a_2, a_3, a_4$ nằm trong khoảng từ $1$ đến $p - 1$.
• Giải phương trình $a_1x_1 + a_2x_2 + a_3x_3 + a_4x_4 \equiv m \pmod{p}$, với $x_i \ge 0$.

Bài toán này quá đơn giản đối với bạn, người đã học qua khóa Nhập môn Lý thuyết Kubic. Vì vậy, Little Cyan Fish đưa thêm cho bạn bốn số nguyên $b_1, b_2, b_3, b_4$. Little Cyan Fish muốn bạn tìm nghiệm sao cho giá trị $b_1x_1 + b_2x_2 + b_3x_3 + b_4x_4$ là nhỏ nhất trong khi vẫn thỏa mãn phương trình trên.

Dữ liệu vào

Có nhiều bộ dữ liệu. Dòng đầu tiên của dữ liệu vào chứa một số nguyên duy nhất $T$ ($1 \le T \le 10^4$), biểu thị số lượng bộ dữ liệu.

Đối với mỗi bộ dữ liệu, dòng đầu tiên chứa hai số nguyên $p$ và $m$ ($2 \le p \le 1.01 \times 10^9$, $0 \le m < p$, đảm bảo $p$ là số nguyên tố).

Dòng tiếp theo chứa bốn số nguyên $a_1, a_2, a_3, a_4$ ($1 \le a_1, a_2, a_3, a_4 < p$).

Dòng tiếp theo chứa bốn số nguyên $b_1, b_2, b_3, b_4$ ($1 \le b_1, b_2, b_3, b_4 \le 10^9$).

Đảm bảo rằng tổng của $\sqrt{p}$ trên tất cả các bộ dữ liệu không vượt quá $2^{17}$.

Dữ liệu ra

Đối với mỗi bộ dữ liệu, in ra một dòng duy nhất chứa một số nguyên, biểu thị giá trị nhỏ nhất của $b_1x_1 + b_2x_2 + b_3x_3 + b_4x_4$.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

199
76000000000
187