Little Cyan Fish طالب يدرس في جامعة كوبيك القوية (PKU). في عام 2023، أخذ Little Cyan Fish مقرر «مقدمة في نظرية كوبيك» الذي يدرّسه البروفيسور كوبيك. بعد إثبات مبرهنة كوبيك الأربعة، أصبح 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