وصف المسألة

لقد تعبت من الكتابة، لا أريد أن أكتب بعد الآن.

"هذا ما يُسمى 'التعب'."

بالنظر إلى متتالية $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