Estoy cansado de escribir; ya no quiero escribir más.

«A esto se le llama estar “cansado”.»

Se da una secuencia $a_1,a_2\ldots a_n$ de longitud $n$. Cada posición $i$ tiene un coste de modificación $c_i$. Para una posición, puedes pagar el coste $c_i$ para cambiar $a_i$ a cualquier valor. Quieres minimizar el coste total de forma que ninguna suma de prefijo de la secuencia sea divisible por $r$.

Formalmente, sea $s_i=\sum_{j=1}^{i}a_j$. Debes asegurarte de que, para la secuencia modificada, se cumpla $s_i \bmod r \ne 0$ para todo $1 \le i \le n$.

Entrada

La primera línea contiene el número de casos de prueba $T$ ($1 \le T \le 10^5$).

Para cada caso de prueba, la primera línea contiene dos enteros positivos $n,r$ ($1 \le n \le 5\cdot 10^5$, $2 \le r \le 10^9$).

La siguiente línea contiene $n$ enteros no negativos $a_i$ ($0 \le a_i < r$), que representan la secuencia.

La siguiente línea contiene $n$ enteros no negativos $c_i$ ($0 \le c_i \le 10^9$), que representan los costes de modificación.

Se garantiza que la suma de todos los $n$ no supera $5\cdot 10^5$.

Salida

Para cada caso de prueba, imprime en una línea un entero que represente el coste mínimo.

Ejemplos

Entrada 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

Salida 1

2
3
2
10
2