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~]$.

h2. Date de intrare

Fişierul de intrare $maestru.in$ ...

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~]$.

h2. Date de ieşire

În fişierul de ieşire $maestru.out$ ...

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
* $3 ≤ N ≤ 5000$
* $3 ≤ P ≤ 10^9^$
* $1 ≤ x[~i~] ≤ 10^9^$

* atat pozitiile pietrelor in fisierul de intrare, cat si pozitiile oricaror noi pietre adaugate sunt obligatoriu distincte doua cate doua

h2. Exemplu