Условие задачи

Я устал писать, я больше не хочу писать.

«Это называется „устал“».

Дана последовательность $a_1,a_2\ldots a_n$ длины $n$, каждая позиция $i$ имеет стоимость изменения $c_i$. Для позиции вы можете заплатить стоимость $c_i$, чтобы изменить $a_i$ на любое значение. Вы хотите минимизировать общую стоимость так, чтобы ни одна префиксная сумма последовательности не делилась на $r$.

Формально, пусть $s_i=\sum_{j=1}^{i}a_j$. Вам нужно добиться того, чтобы для изменённой последовательности для всех $1 \le i \le n$ выполнялось $s_i \bmod r \ne 0$.

Входные данные

Первая строка содержит количество наборов входных данных $T$ ($1 \le T \le 10^5$).

Для каждого набора входных данных первая строка содержит два положительных целых числа $n,r$ ($1 \le n \le 5\cdot 10^5$, $2 \le r \le 10^9$).

Следующая строка содержит $n$ неотрицательных целых чисел $a_i$ ($0 \le a_i < r$), задающих последовательность.

Следующая строка содержит $n$ неотрицательных целых чисел $c_i$ ($0 \le c_i \le 10^9$), задающих стоимости изменения.

Гарантируется, что сумма всех $n$ не превосходит $5\cdot 10^5$.

Выходные данные

Для каждого набора входных данных выведите в отдельной строке одно целое число — минимальную стоимость.

Примеры

Входные данные 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

Выходные данные 1

2
3
2
10
2