J. Skating With Alysa Liu
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Alysa Liu is sad and looking for someone to skate with her. However she gives a problem to you before you can skate with her. Solve it fast so you can have more time on the ice with Alysa Liu!

The input has an integer and $$$n$$$ ($$$1\le n\le 5\cdot10^{5}$$$). There are $$$n$$$ integers in an array. For each $$$i$$$, there is $$$a_{i}$$$ ($$$1\le a_{i}\le 10^{9}$$$). You also have another integer $$$m$$$ ($$$1\le m\le 10^{9}$$$).

Furthermore, you have an ice skate of size $$$k$$$ ($$$1\le k\le n$$$) that allows you to increment any range $$$[l, r]$$$ of length $$$k$$$ ($$$1\le l\le r\le n,$$$ $$$r - l + 1 = k$$$) in the array by a positive integer $$$x$$$ ($$$1 \le x$$$).

After an arbitrary amount of operations, you want to maximize $$$\sum_{i=1}^{n}{(a_{i} \bmod m)}$$$. Print the maximum value. If you solve this problem you will become partners with Alysa Liu and she won't be sad anymore!

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^{4}$$$). The description of each test case follows.

The first line will contain $$$n$$$, $$$m$$$, and $$$k$$$.

The second line will contain $$$n$$$ integers, the $$$i$$$th describing $$$a_i$$$.

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

Output

Print the answer to maximize $$$\sum_{i=1}^{n}{(a_{i} \bmod m)}$$$ after an arbitrary amount of operations.

Example
Input
4
3 10 3
5 8 2
4 3 2
1 1 1 1
5 13 2
1 1 1 1 1
10 1 3
6 7 6 7 6 7 6 7 6 7
Output
18
8
58
0
Note

In the first testcase, it is optimal to perform one operation and by making $$$x = 1$$$ so that the resulting array becomes $$$[6, 9, 3]$$$ which has a resulting sum of $$$18$$$ when each element is taken under $$$\bmod 10$$$.

In the second testcase, an optimal array after all operations is $$$[2, 2, 2, 2]$$$ which gives the resulting sum of $$$8$$$.

In the third testcase, an optimal array after all operations in $$$[12, 23, 12, 12, 12]$$$ which gives the resulting sum of $$$58$$$ after each element is taken under $$$\bmod 13$$$.

In the fourth testcase, any array after any operations is optimal.