Legenda spune ca maestrul Su Elf-chi a capatat insasi de la zei tainele unei licori magice cu puteri formidabile menite sa $“bucure sufletul”$. Singurul legamant pe care acesta il avea de asumat era acela de a nu depasi anumite concentratii de consum ale acesteia pentru a nu dezlantui haosul in univers. Secole de-a randul omenirea a trait in pace si prosperitate. Acest lucru avea insa sa se schimbe odata cu aparitia cazanelor de arama. Licoarea s-a dezlantuit si a inceput sa capete forme malefice zapacind mintile oamenilor si osandindu-i la chinuri vesnice. Singura sansa de salvare a omenirii a fost ca maestrul sa faca hatarul zeilor si sa duca la bun sfarsit incercarile acestora.
Se facea ca prima incercare era aceea de a traversa un rau cu totul si cu totul din apa. Zeii au plasat pe acest rau un numar de pietre N pe care maestrul sa poata sari o singura data inainte ca acestea sa se scufunde. Pozitiile pietrelor sunt date sub forma unui sir sortat de numere intregi $x[~1~], x[~2~], … x[~N~]$ , unde $x[~1~]$ si $x[~N~]$ reprezinta marginile din stanga si din dreapta ale raului.
Se facea ca prima incercare era aceea de a traversa un rau cu totul si cu totul din apa. Zeii au plasat pe acest rau un numar de pietre $N$ pe care maestrul sa poata sari o singura data inainte ca acestea sa se scufunde. Pozitiile pietrelor sunt date sub forma unui sir sortat de numere intregi $x[~1~], x[~2~], … x[~N~]$ , unde $x[~1~]$ si $x[~N~]$ reprezinta marginile din stanga si din dreapta ale raului.
Tocmai iesit fiind din meditatia transcedentala, maestrul poate sari de pe o piatra pe alta doar daca distanta dintre ele este cel mult o valoare $P$ data, scopul sau fiind de a ajunge de pe malul stang notat cu $x[~1~]$ pe cel drept notat cu $x[~N~]$ si inapoi la $x[~1~]$.
Tocmai iesit fiind din meditatia transcedentala, maestrul poate sari de pe o piatra pe alta doar daca distanta dintre ele este cel mult o valoare $P$ data, unde prin distanta intelegem $x[~j~]-x[~i~]$, oricare ar fi $i$ si $j$ cu $i<j$, scopul sau fiind de a ajunge de pe malul stang notat cu $x[~1~]$ pe cel drept notat cu $x[~N~]$ si inapoi la $x[~1~]$.
Noi stim ca numarul de pietre este insuficient ca maestrul sa indeplineasca aceasta sarcina, insa vedeniile provocate de licoarea melefica i-au intunecat ratiunea. Este de datoria voastra sa interveniti si sa adaugati un numar minim de pietre si sa il salvati pe maestru de la osanda atingerii apei.
h2. Date de intrare
Pe prima linie a fisierului de intrare se gaseste T, numarul de teste. Pe prima linie a fiecarui test se afla numerele $N$ si $P$, urmand ca pe linia imediat urmatoare sa fie descris sirul $x[~1~], x[~2~], … x[~N~]$.
Pe prima linie a fisierului de intrare se gaseste $T$, numarul de teste. Pe prima linie a fiecarui test se afla numerele $N$ si $P$, urmand ca pe linia imediat urmatoare sa fie descris sirul sortat $x[~1~], x[~2~], … x[~N~]$.
h2. Date de ieşire
In fisierul de iesire se vor afisa T linii, pe fiecare dintre acestea un intreg reprezetand numarul minim de pietre ce trebuiesc adaugate. Daca exista o configuratie prin care se pot adauga numarul minim de pietre indicat in asa fel incat maestrul sa-si poate realiza drumul, solutia se considera corecta.
In fisierul de iesire se vor afisa $T$ linii, pe fiecare dintre acestea un intreg reprezetand numarul minim de pietre ce trebuiesc adaugate. Daca exista o configuratie prin care se pot adauga numarul minim de pietre indicat in asa fel incat maestrul sa-si poate realiza drumul, solutia se considera corecta.
h2. Restricţii
* $1 ≤ T ≤ 4000$
* $3 ≤ N ≤ 5000$
* $3 ≤ P ≤ 10^9^$
* $1 ≤ x[~i~] ≤ 10^9^$
