Tehtävänanto

Olen väsynyt kirjoittamaan, en halua kirjoittaa enää.

"Tätä kutsutaan 'väsymykseksi'."

Annettuna on pituutta $n$ oleva lukujono $a_1,a_2\ldots a_n$, jossa jokaisella kohdalla $i$ on muokkauskustannus $c_i$. Voit maksaa kohdassa kustannuksen $c_i$ muuttaaksesi luvun $a_i$ miksi tahansa arvoksi. Haluat minimoida kokonaiskustannuksen siten, että mikään lukujonon etuliitesumma ei ole jaollinen luvulla $r$.

Muodollisesti, olkoon $s_i=\sum_{j=1}^{i}a_j$. Sinun tulee varmistaa, että muokatulle lukujonolle pätee kaikilla $1 \le i \le n$ ehto $s_i \bmod r \ne 0$.

Syöte

Ensimmäinen rivi sisältää testitapausten lukumäärän $T$ ($1 \le T \le 10^5$).

Jokaista testitapausta kohden ensimmäinen rivi sisältää kaksi positiivista kokonaislukua $n,r$ ($1 \le n \le 5\cdot 10^5$, $2 \le r \le 10^9$).

Seuraava rivi sisältää $n$ epänegatiivista kokonaislukua $a_i$ ($0 \le a_i < r$), jotka esittävät lukujonoa.

Seuraava rivi sisältää $n$ epänegatiivista kokonaislukua $c_i$ ($0 \le c_i \le 10^9$), jotka esittävät muokkauskustannuksia.

On taattu, että kaikkien lukujen $n$ summa on enintään $5\cdot 10^5$.

Tuloste

Tulosta jokaista testitapausta kohden omalle rivilleen yksi kokonaisluku, joka ilmaisee pienimmän kustannuksen.

Esimerkit

Syöte 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

Tuloste 1

2
3
2
10
2