Descrizione

Sono stanco di scrivere, non voglio più scrivere.

"Questo si chiama essere 'stanchi'."

Data una sequenza $a_1,a_2\ldots a_n$ di lunghezza $n$, ogni posizione $i$ ha un costo di modifica $c_i$. Per una posizione, puoi pagare il costo $c_i$ per cambiare $a_i$ in qualsiasi valore. Vuoi minimizzare il costo totale in modo che nessuna somma prefissa della sequenza sia divisibile per $r$.

Formalmente, sia $s_i=\sum_{j=1}^{i}a_j$. Devi assicurarti che per la sequenza modificata, per tutti gli $1 \le i \le n$, valga $s_i \bmod r \ne 0$.

Input

La prima riga contiene il numero di casi di test $T$ ($1 \le T \le 10^5$).

Per ogni caso di test, la prima riga contiene due interi positivi $n,r$ ($1 \le n \le 5\cdot 10^5$, $2 \le r \le 10^9$).

La riga successiva contiene $n$ interi non negativi $a_i$ ($0 \le a_i < r$), che rappresentano la sequenza.

La riga successiva contiene $n$ interi non negativi $c_i$ ($0 \le c_i \le 10^9$), che rappresentano i costi di modifica.

È garantito che la somma di tutti gli $n$ non supera $5\cdot 10^5$.

Output

Per ogni caso di test, stampa un intero su una singola riga, che rappresenta il costo minimo.

Esempi

Input 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

Output 1

2
3
2
10
2