我累了，我不想再写了。

“这就叫‘累了’。”

给定一个长度为 $n$ 的序列 $a_1, a_2 \dots 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 \neq 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