תיאור הבעיה

נמאס לי לכתוב, אני לא רוצה לכתוב יותר.

"לזה קוראים 'עייף'."

נתונה סדרה $a_1,a_2\ldots a_n$ באורך $n$, ולכל מיקום $i$ יש עלות שינוי $c_i$. עבור מיקום כלשהו, ניתן לשלם את העלות $c_i$ כדי לשנות את $a_i$ לכל ערך שהוא. ברצונך למזער את העלות הכוללת כך שאף סכום רישא של הסדרה לא יתחלק ב-$r$.

באופן פורמלי, יהי $s_i=\sum_{j=1}^{i}a_j$. עליך לוודא שעבור הסדרה לאחר השינוי, לכל $1 \le i \le n$, מתקיים $s_i \bmod r \ne 0$.

קלט

השורה הראשונה מכילה את מספר מקרי הבדיקה $T$ ($1 \le T \le 10^5$).

עבור כל מקרה בדיקה, השורה הראשונה מכילה שני מספרים שלמים חיוביים $n,r$ ($1 \le n \le 5\cdot 10^5$, $2 \le r \le 10^9$).

השורה הבאה מכילה $n$ מספרים שלמים אי-שליליים $a_i$ ($0 \le a_i < r$), המייצגים את הסדרה.

השורה הבאה מכילה $n$ מספרים שלמים אי-שליליים $c_i$ ($0 \le c_i \le 10^9$), המייצגים את עלויות השינוי.

מובטח כי סכום כל ערכי ה-$n$ אינו עולה על $5\cdot 10^5$.

פלט

עבור כל מקרה בדיקה, הדפס מספר שלם אחד בשורה נפרדת, המייצג את העלות המינימלית.

דוגמאות

קלט 1

5
3 3
2 1 2
3 2 1
4 2
0 1 0 0
2 1 3 1
5 3
2 1 1 0 2
3 2 4 1 5
6 3
0 2 1 1 2 0
6 2 4 5 5 1
7 4
1 2 3 0 1 2 3
3 4 1 7 5 2 3

פלט 1

2
3
2
10
2