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