Little Cyan Fish adalah seorang mahasiswa yang belajar di Powerful Kubic University (PKU). Pada tahun 2023, Little Cyan Fish mengambil mata kuliah Pengantar Teori Kubic yang diajarkan oleh Prof. Kubic. Setelah membuktikan Teorema Empat Kubic, Little Cyan Fish menjadi asisten dosen untuk mata kuliah ini. Dalam ujian akhir mata kuliah ini, Little Cyan Fish menyiapkan persoalan kecil yang menarik berikut:

• Diberikan sebuah bilangan prima $p$ dan empat bilangan bulat $a_1, a_2, a_3, a_4$ antara $1$ dan $p - 1$.
• Selesaikan persamaan $a_1x_1 + a_2x_2 + a_3x_3 + a_4x_4 \equiv m \pmod p$, di mana $x_i \ge 0$.

Persoalan ini terlalu mudah bagi Anda yang telah mengambil mata kuliah Pengantar Teori Kubic. Oleh karena itu, Little Cyan Fish memberikan empat bilangan bulat lainnya $b_1, b_2, b_3, b_4$. Little Cyan Fish ingin solusi Anda meminimalkan nilai dari $b_1x_1 + b_2x_2 + b_3x_3 + b_4x_4$ sembari tetap memenuhi persamaan di atas.

Masukan

Terdapat beberapa kasus uji. Baris pertama dari masukan berisi sebuah bilangan bulat $T$ ($1 \le T \le 10^4$), yang menyatakan banyaknya kasus uji.

Untuk setiap kasus uji, baris pertama dari masukan berisi dua bilangan bulat $p$ dan $m$ ($2 \le p \le 1.01 \times 10^9, 0 \le m < p$, dijamin bahwa $p$ adalah bilangan prima).

Baris berikutnya berisi empat bilangan bulat $a_1, a_2, a_3, a_4$ ($1 \le a_1, a_2, a_3, a_4 < p$).

Baris berikutnya berisi empat bilangan bulat $b_1, b_2, b_3, b_4$ ($1 \le b_1, b_2, b_3, b_4 \le 10^9$).

Dijamin bahwa jumlah dari $\lceil \sqrt{p} \rceil$ di semua kasus uji tidak melebihi $2^{17}$.

Keluaran

Untuk setiap kasus uji, cetak satu baris yang berisi satu bilangan bulat, yang menyatakan nilai minimum dari $b_1x_1 + b_2x_2 + b_3x_3 + b_4x_4$.

Contoh

Masukan 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

Keluaran 1

199
76000000000
187