Opis problemu

Jestem zmęczony pisaniem, nie chcę już więcej pisać.

„To się nazywa »zmęczenie«.”

Dany jest ciąg $a_1,a_2\ldots a_n$ o długości $n$, w którym każda pozycja $i$ ma koszt modyfikacji $c_i$. Dla danej pozycji możesz zapłacić koszt $c_i$, aby zmienić $a_i$ na dowolną wartość. Chcesz zminimalizować łączny koszt tak, aby żadna suma prefiksowa ciągu nie była podzielna przez $r$.

Formalnie, niech $s_i=\sum_{j=1}^{i}a_j$. Musisz upewnić się, że dla zmodyfikowanego ciągu, dla wszystkich $1 \le i \le n$, zachodzi $s_i \bmod r \ne 0$.

Wejście

Pierwszy wiersz zawiera liczbę przypadków testowych $T$ ($1 \le T \le 10^5$).

Dla każdego przypadku testowego pierwszy wiersz zawiera dwie dodatnie liczby całkowite $n,r$ ($1 \le n \le 5\cdot 10^5$, $2 \le r \le 10^9$).

Kolejny wiersz zawiera $n$ nieujemnych liczb całkowitych $a_i$ ($0 \le a_i < r$), reprezentujących ciąg.

Następny wiersz zawiera $n$ nieujemnych liczb całkowitych $c_i$ ($0 \le c_i \le 10^9$), reprezentujących koszty modyfikacji.

Gwarantowane jest, że suma wszystkich $n$ nie przekracza $5\cdot 10^5$.

Wyjście

Dla każdego przypadku testowego wypisz w pojedynczym wierszu jedną liczbę całkowitą, oznaczającą minimalny koszt.

Przykłady

Wejście 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

Wyjście 1

2
3
2
10
2