Little Cyan Fish는 Powerful Kubic University(PKU)에서 공부하는 학생입니다. 2023년에 Little Cyan Fish는 Prof. Kubic이 가르치는 "Kubic 이론 입문" 강의를 수강했습니다. Four Kubic Theorem을 증명한 후, Little Cyan Fish는 이 강의의 조교가 되었습니다. 이 강의의 기말고사에서 Little Cyan Fish는 다음과 같은 흥미로운 작은 문제를 준비했습니다.

• 소수 $p$와 $1$부터 $p-1$ 사이의 네 정수 $a_1, a_2, a_3, a_4$가 주어집니다.
• $x_i \ge 0$일 때, 방정식 $a_1x_1 + a_2x_2 + a_3x_3 + a_4x_4 \equiv m \pmod{p}$를 푸세요.

이 문제는 "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$)가 주어집니다.

모든 테스트 케이스에 대해 $\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