Lýsing

Ég er þreyttur á að skrifa, ég vil ekki skrifa meira.

„Þetta kallast að vera ‚þreyttur‘.“

Gefin er runa $a_1,a_2\ldots a_n$ af lengd $n$, þar sem hver staða $i$ hefur breytingarkostnað $c_i$. Fyrir tiltekna stöðu getur þú greitt kostnaðinn $c_i$ til að breyta $a_i$ í hvaða gildi sem er. Þú vilt lágmarka heildarkostnaðinn þannig að engin forskeytissumma rununnar sé deilanleg með $r$.

Formlega, látum $s_i=\sum_{j=1}^{i}a_j$. Þú þarft að tryggja að fyrir breyttu rununa gildi fyrir öll $1 \le i \le n$ að $s_i \bmod r \ne 0$.

Inntak

Fyrsta línan inniheldur fjölda prófunartilvika $T$ ($1 \le T \le 10^5$).

Fyrir hvert prófunartilvik inniheldur fyrsta línan tvær jákvæðar heiltölur $n,r$ ($1 \le n \le 5\cdot 10^5$, $2 \le r \le 10^9$).

Næsta lína inniheldur $n$ óneikvæðar heiltölur $a_i$ ($0 \le a_i < r$), sem tákna rununa.

Næsta lína inniheldur $n$ óneikvæðar heiltölur $c_i$ ($0 \le c_i \le 10^9$), sem tákna breytingarkostnaðinn.

Tryggt er að summa allra $n$ fari ekki yfir $5\cdot 10^5$.

Úttak

Fyrir hvert prófunartilvik skal prenta eina heiltölu í stakri línu, sem táknar lágmarkskostnaðinn.

Dæmi

Inntak 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

Úttak 1

2
3
2
10
2