Little Cyan Fish เป็นนักศึกษาที่กำลังศึกษาอยู่ที่ Powerful Kubic University (PKU) ในปี 2023 Little Cyan Fish ได้ลงเรียนวิชาความรู้เบื้องต้นเกี่ยวกับทฤษฎีคูบิก (Introduction to the Kubic Theory) ซึ่งสอนโดย ศ. คูบิก (Prof. Kubic) หลังจากพิสูจน์ทฤษฎีบทสี่คูบิก (Four Kubic Theorem) ได้สำเร็จ Little Cyan Fish ก็ได้เป็นผู้ช่วยสอนของวิชานี้ ในการสอบปลายภาคของวิชานี้ Little Cyan Fish ได้เตรียมโจทย์ปัญหาเล็กๆ ที่น่าสนใจดังต่อไปนี้:

• กำหนดจำนวนเฉพาะ $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$

ปัญหานี้ง่ายเกินไปสำหรับคุณที่ได้เรียนวิชาความรู้เบื้องต้นเกี่ยวกับทฤษฎีคูบิกมาแล้ว ดังนั้น 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$)

รับประกันว่าผลรวมของ $\lceil \sqrt{p} \rceil$ ในทุกชุดทดสอบจะไม่เกิน $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