K. K-Coverage
time limit per test
1 с
memory limit per test
1024 megabytes
input
standard input
output
standard output

Panda has a one-dimensional axis with $$$n$$$ segments placed on its non-negative side. The left endpoint of the $$$i$$$-th segment is $$$l_i$$$. Every segment has the same length, $$$L$$$. This means the $$$i$$$-th segment covers the interval $$$[l_i, l_i+L-1]$$$ (inclusive).

Now, Panda wants you to find the maximum number of integer points on the non-negative side of the axis that can be covered exactly $$$k$$$ times after moving at most one segment. Specifically, you are allowed to select at most one segment and change its left endpoint to any non-negative integer (with no upper bound). The segment's length, $$$L$$$, remains the same.

Input

The first line contains an integer $$$T$$$ ($$$1\le T\le 2\times 10^5$$$), denoting the number of test cases.

For each test case, the first line contains three positive integers $$$n, L, k$$$ ($$$1\le n\le 2\times 10^5$$$, $$$1\le L\le n$$$, $$$1\le k\le n$$$). $$$n$$$ is the total number of segments, $$$L$$$ is the fixed length of every segment, and $$$k$$$ is the required coverage count.

The second line contains $$$n$$$ non-negative integers. The $$$i$$$-th integer is $$$l_i$$$ ($$$0\le l_i\le 2 \times n$$$) representing the left endpoint of the $$$i$$$-th segment.

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

Output

For each test case, output one line with a single integer, denoting the maximum number of integer points that can be covered exactly $$$k$$$ times after moving at most one segment.

Example
Input
3
3 2 1
2 6 2
3 3 2
6 2 0
5 1 3
5 6 7 8 9
Output
6
3
0
Note

For the first test case in the example, initially, the three segments are $$$[2,3]$$$, $$$[6,7]$$$, and $$$[2,3]$$$. You can change the third segment's left endpoint to $$$114514$$$. After this move, the segments are $$$[2,3]$$$, $$$[6,7]$$$, and $$$[114514,114515]$$$. This results in 6 integer points covered exactly once, which is the maximum achievable.

For the second test case, you can move the first segment's left endpoint to $$$3$$$ to maximize the number of integer points that are covered exactly twice.