書くことに疲れてしまった。もう書きたくない。

「これが『疲れた』ということだ。」

長さ $n$ の数列 $a_1,a_2\ldots a_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$)。

各テストケースの最初の行には $2$ つの正の整数 $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$ 行に出力してください。

入出力例

入力 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