Panda memiliki sebuah sumbu satu dimensi dengan $n$ segmen yang ditempatkan pada sisi non-negatifnya. Titik ujung kiri dari segmen ke-$i$ adalah $l_i$. Setiap segmen memiliki panjang yang sama, yaitu $L$. Ini berarti segmen ke-$i$ mencakup interval $[l_i, l_i + L - 1]$ (inklusif).

Sekarang, Panda ingin Anda mencari jumlah maksimum titik bilangan bulat pada sisi non-negatif sumbu tersebut yang dapat tercakup tepat $k$ kali setelah memindahkan paling banyak satu segmen. Secara spesifik, Anda diperbolehkan memilih paling banyak satu segmen dan mengubah titik ujung kirinya menjadi bilangan bulat non-negatif berapa pun (tanpa batas atas). Panjang segmen tersebut, $L$, tetap sama.

Masukan

Baris pertama berisi sebuah bilangan bulat $T$ ($1 \le T \le 2 \times 10^5$), yang menyatakan jumlah kasus uji.

Untuk setiap kasus uji, baris pertama berisi tiga bilangan bulat positif $n, L, k$ ($1 \le n \le 2 \times 10^5$, $1 \le L \le n$, $1 \le k \le n$). $n$ adalah jumlah total segmen, $L$ adalah panjang tetap dari setiap segmen, dan $k$ adalah jumlah cakupan yang diminta.

Baris kedua berisi $n$ bilangan bulat non-negatif. Bilangan bulat ke-$i$ adalah $l_i$ ($0 \le l_i \le 2 \times n$) yang menyatakan titik ujung kiri dari segmen ke-$i$.

Dijamin bahwa jumlah nilai $n$ di seluruh kasus uji tidak melebihi $2 \times 10^5$.

Keluaran

Untuk setiap kasus uji, keluarkan satu baris berisi satu bilangan bulat yang menyatakan jumlah maksimum titik bilangan bulat yang dapat tercakup tepat $k$ kali setelah memindahkan paling banyak satu segmen.

Contoh

Masukan 1

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

Keluaran 1

6
3
0

Catatan

Untuk kasus uji pertama pada contoh, awalnya ketiga segmen tersebut adalah $[2, 3]$, $[6, 7]$, dan $[2, 3]$. Anda dapat mengubah titik ujung kiri segmen ketiga menjadi $114514$. Setelah pemindahan ini, segmen-segmennya menjadi $[2, 3]$, $[6, 7]$, dan $[114514, 114515]$. Hal ini menghasilkan $6$ titik bilangan bulat yang tercakup tepat satu kali, yang merupakan nilai maksimum yang dapat dicapai.

Untuk kasus uji kedua, Anda dapat memindahkan titik ujung kiri segmen pertama ke $3$ untuk memaksimalkan jumlah titik bilangan bulat yang tercakup tepat dua kali.