I'm tired of writing, I don't want to write anymore.

"This is called 'tired'."

Given a sequence $a_1,a_2\ldots a_n$ of length $n$, each position $i$ has a modification cost $c_i$. For a position, you can pay the cost $c_i$ to change $a_i$ into any value. You want to minimize the total cost so that every prefix sum of the sequence is not divisible by $r$.

Formally, let $s_i=\sum_{j=1}^{i}a_j$. You need to make sure that for the modified sequence, for all $1 \le i \le n$, $s_i \bmod r \ne 0$.

Input

The first line contains the number of test cases $T$ ($1 \le T \le 10^5$).

For each test case, the first line contains two positive integers $n,r$ ($1 \le n \le 5\cdot 10^5$, $2 \le r \le 10^9$).

The next line contains $n$ non-negative integers $a_i$ ($0 \le a_i < r$), representing the sequence.

The next line contains $n$ non-negative integers $c_i$ ($0 \le c_i \le 10^9$), representing the modification costs.

It is guaranteed that the sum of all $n$ does not exceed $5\cdot 10^5$.

Output

For each test case, output one integer in a single line, representing the minimum cost.

Examples

Input 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

Output 1

2
3
2
10
2