Énoncé

Je suis fatigué d'écrire, je ne veux plus écrire.

« C'est ce qu'on appelle être "fatigué". »

Étant donné une suite $a_1,a_2\ldots a_n$ de longueur $n$, chaque position $i$ a un coût de modification $c_i$. Pour une position donnée, vous pouvez payer le coût $c_i$ afin de remplacer $a_i$ par n'importe quelle valeur. Vous souhaitez minimiser le coût total de sorte qu'aucune somme préfixe de la suite ne soit divisible par $r$.

Formellement, soit $s_i=\sum_{j=1}^{i}a_j$. Vous devez vous assurer que pour la suite modifiée, pour tout $1 \le i \le n$, on ait $s_i \bmod r \ne 0$.

Entrée

La première ligne contient le nombre de cas de test $T$ ($1 \le T \le 10^5$).

Pour chaque cas de test, la première ligne contient deux entiers strictement positifs $n,r$ ($1 \le n \le 5\cdot 10^5$, $2 \le r \le 10^9$).

La ligne suivante contient $n$ entiers naturels $a_i$ ($0 \le a_i < r$), représentant la suite.

La ligne suivante contient $n$ entiers naturels $c_i$ ($0 \le c_i \le 10^9$), représentant les coûts de modification.

Il est garanti que la somme de tous les $n$ ne dépasse pas $5\cdot 10^5$.

Sortie

Pour chaque cas de test, affichez un entier sur une seule ligne, représentant le coût minimal.

Exemples

Entrée 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

Sortie 1

2
3
2
10
2