Пандада теріс емес бөлігінде $n$ кесінді орналасқан бір өлшемді сан осі бар. $i$-ші кесіндінің сол жақ шеткі нүктесі $l_i$ тең. Барлық кесінділердің ұзындығы бірдей, $L$-ге тең. Бұл $i$-ші кесінді $[l_i, l_i + L - 1]$ аралығын (шеткі нүктелерін қоса алғанда) жабатынын білдіреді.

Енді Панда сізден ең көп дегенде бір кесіндіні жылжытқаннан кейін осьтің теріс емес бөлігінде дәл $k$ рет жабылуы мүмкін бүтін нүктелердің ең көп санын табуды сұрайды. Нақтырақ айтқанда, сізге ең көп дегенде бір кесіндіні таңдап, оның сол жақ шеткі нүктесін кез келген теріс емес бүтін санға (жоғарғы шекарасыз) өзгертуге рұқсат етіледі. Кесіндінің ұзындығы $L$ өзгеріссіз қалады.

Кіріс деректері

Бірінші жолда тест жағдайларының санын білдіретін бір бүтін сан $T$ ($1 \le T \le 2 \times 10^5$) берілген.

Әрбір тест жағдайы үшін бірінші жолда үш оң бүтін сан $n, L, k$ ($1 \le n \le 2 \times 10^5$, $1 \le L \le n$, $1 \le k \le n$) берілген. $n$ — кесінділердің жалпы саны, $L$ — әрбір кесіндінің тұрақты ұзындығы, ал $k$ — талап етілетін жабу саны.

Екінші жолда $n$ теріс емес бүтін сан берілген. $i$-ші бүтін сан $l_i$ ($0 \le l_i \le 2 \times n$) — $i$-ші кесіндінің сол жақ шеткі нүктесі.

Барлық тест жағдайлары бойынша $n$ сандарының қосындысы $2 \times 10^5$ мәнінен аспайтынына кепілдік беріледі.

Шығыс деректері

Әрбір тест жағдайы үшін ең көп дегенде бір кесіндіні жылжытқаннан кейін дәл $k$ рет жабылуы мүмкін бүтін нүктелердің ең көп санын білдіретін бір бүтін саннан тұратын бір жолды шығарыңыз.

Мысалдар

Кіріс деректері 1

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

Шығыс деректері 1

6
3
0

Ескертпе

Мысалдағы бірінші тест жағдайы үшін бастапқыда үш кесінді $[2, 3]$, $[6, 7]$ және $[2, 3]$ болып табылады. Үшінші кесіндінің сол жақ шеткі нүктесін $114514$ мәніне өзгертуге болады. Осы жүрістен кейін кесінділер $[2, 3]$, $[6, 7]$ және $[114514, 114515]$ болады. Нәтижесінде $6$ бүтін нүкте дәл бір рет жабылады, бұл қол жеткізуге болатын ең үлкен мән.

Екінші тест жағдайы үшін дәл екі рет жабылатын бүтін нүктелердің санын барынша арттыру үшін бірінші кесіндінің сол жақ шеткі нүктесін $3$-ке жылжытуға болады.