Умова задачі

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

«Це називається „втомився“».

Дано послідовність $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