POLSKI SPOJ

Kanonier Jaś, po wspaniałym występie w Bajtlandzkich Igrzyskach Wojskowych, otrzymał propozycję awansu na stopień bombardiera. Ponieważ w wojsku Bajtlandii, oprócz umiejętności praktycznych, liczy się również wiedza teoretyczna, Jaś musiał zdać odpowiedni egzamin.

Jedno z zadań na egzaminie polegało na wyznaczeniu prędkości obrotowej obracającej się (przeciwnie do wskazówek zegara) platformy, na której umieszczone zostało strzalające w równych odstępach czasu działo. Dla każdego strzału zapamiętywana była wartość k < n wskazująca na kąt 0 <= 2*PI*k/n < 2*PI wyznaczający kierunek, w którym został on oddany. Wartość n jest wspólna dla wszystkich kątów. Zakładać będziemy, że żadne dwa strzały nie zostały oddane w tym samym kierunku.

Wejście

W pierwszej linii podana została liczba testów t <= 10. W pierwszej linii każdego zestawu testowego podana została para liczb m n, oznaczająca odpowiednio liczbę strzałów oraz wartość mianownika potrzebną do wyznaczenia kątów. W drugiej linii zestawu testowego podane zostały wartości k dla wszystkich kątów, posortowane w porządku rosnącym. Przyjmiemy ograniczenia: 2 <= m < n <= 5000.

Wyjście

Dla każdego testu należy wyznaczyć minimalną wartość prędkości obrotowej platformy, z której mogły nastąpić zadane kątami strzały. Podana na wyjściu liczba całkowita a wskazywać będzie na prędkość obrotową równą 2*PIa/n [1/s].

Przykład

Wejście:
4
2 4
0 3
3 7
0 2 5
5 15
0 4 7 8 11
3 9
1 4 7

Wyjście:
1
2
4
3