Panda có một trục tọa độ một chiều với $n$ đoạn thẳng được đặt ở phần không âm của trục. Đầu mút bên trái của đoạn thẳng thứ $i$ là $l_i$. Mọi đoạn thẳng đều có cùng độ dài $L$. Điều này có nghĩa là đoạn thẳng thứ $i$ phủ đoạn $[l_i, l_i + L - 1]$ (bao gồm cả hai đầu mút).

Bây giờ, Panda muốn bạn tìm số lượng tối đa các điểm nguyên trên phần không âm của trục có thể được phủ đúng $k$ lần sau khi di chuyển nhiều nhất một đoạn thẳng. Cụ thể, bạn được phép chọn nhiều nhất một đoạn thẳng và đổi đầu mút bên trái của nó thành bất kỳ số nguyên không âm nào (không có giới hạn trên). Độ dài $L$ của đoạn thẳng vẫn giữ nguyên.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $T$ ($1 \le T \le 2 \times 10^5$), biểu thị số lượng bộ dữ liệu.

Với mỗi bộ dữ liệu, dòng đầu tiên chứa ba số nguyên dương $n, L, k$ ($1 \le n \le 2 \times 10^5$, $1 \le L \le n$, $1 \le k \le n$). $n$ là tổng số đoạn thẳng, $L$ là độ dài cố định của mỗi đoạn thẳng, và $k$ là số lần phủ theo yêu cầu.

Dòng thứ hai chứa $n$ số nguyên không âm. Số nguyên thứ $i$ là $l_i$ ($0 \le l_i \le 2 \times n$) biểu thị đầu mút bên trái của đoạn thẳng thứ $i$.

Dữ liệu đảm bảo tổng của $n$ trên tất cả các bộ dữ liệu không vượt quá $2 \times 10^5$.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một dòng chứa một số nguyên duy nhất, biểu thị số lượng tối đa các điểm nguyên có thể được phủ đúng $k$ lần sau khi di chuyển nhiều nhất một đoạn thẳng.

Ví dụ

Dữ liệu vào 1

3
3 2 1
2 6 2
3 3 2
6 2 0
5 1 3
5 6 7 8 9

Dữ liệu ra 1

6
3
0

Ghi chú

Đối với bộ dữ liệu đầu tiên trong ví dụ, ban đầu ba đoạn thẳng là $[2, 3]$, $[6, 7]$ và $[2, 3]$. Bạn có thể đổi đầu mút bên trái của đoạn thẳng thứ ba thành $114514$. Sau bước di chuyển này, các đoạn thẳng là $[2, 3]$, $[6, 7]$ và $[114514, 114515]$. Kết quả là có $6$ điểm nguyên được phủ đúng một lần, đây là giá trị lớn nhất có thể đạt được.

Đối với bộ dữ liệu thứ hai, bạn có thể di chuyển đầu mút bên trái của đoạn thẳng thứ nhất đến $3$ để tối đa hóa số lượng điểm nguyên được phủ đúng hai lần.