글을 쓰는 데 지쳤다. 더 이상 쓰고 싶지 않다.

“이것을 ‘지쳤다’고 한다.”

길이가 $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$).

각 테스트 케이스의 첫 번째 줄에는 두 양의 정수 $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