Mały A i mały S są kolegami z drużyny ACM. Mały A ma bardzo dobry wzrok i często potrafi dostrzec dziwne prawidłowości w danych.

Podczas pewnego treningu mały S narysował na kartce koło. Mały A rzucił na nie okiem i powiedział: „Przecież to jest siedemnastokąt foremny!”. Następnie wyciągnął wiele obrazków z wielokątami foremnymi, aby mały S mógł je poobserwować. Mały S nie miał jednak pojęcia, o co chodzi, więc poprosił cię o pomoc w identyfikacji.

Mówiąc konkretnie, mając daną maksymalną liczbę boków wielokąta $n$, mały A wygenerował $N$ punktów na płaszczyźnie w następujący sposób:

• Najpierw wybierany jest punkt $(x,y)$ jako środek. Punkt ten może być ustalony jako $(0, 0)$ lub wybrany jednostajnie z obszaru $[-1,1] \times [-1,1]$.
• Losowo wybierana jest liczba całkowita $k$ z przedziału $[\max(3, n-5),n]$.
• Rozważane jest koło o środku $(x, y)$ i promieniu $1$. Wybierany jest jednostajnie losowy wielokąt foremny o $k$ bokach wpisany w to koło.
• Proces powtarza się $N$ razy: za każdym razem wybierany jest jednostajnie losowy punkt $u$ na brzegu wielokąta foremnego o $k$ bokach, a do danych dodawany jest punkt $\hat u=u+\mathcal N$. Tutaj $\mathcal N$ to szum losowy, którego obie współrzędne niezależnie podlegają rozkładowi Gaussa ze średnią $0$ i odchyleniem standardowym $0.01$.
• Wszystkie powyższe procesy losowe są niezależne.

Musisz na podstawie tych $N$ punktów odtworzyć liczbę boków wielokąta $k$.

Wejście

Dane wczytywane są ze standardowego wejścia.

Zadanie zawiera wiele zestawów danych testowych. Pierwsza linia zawiera liczbę całkowitą $T$, oznaczającą liczbę zestawów danych.

Dla każdego zestawu danych pierwsza linia zawiera dwie liczby całkowite $N,n$, oznaczające liczbę punktów oraz maksymalną możliwą liczbę boków wielokąta. Następnie $N$ linii, z których każda zawiera dwie liczby zmiennoprzecinkowe $\hat u_x, \hat u_y$, oznaczające współrzędne punktu $\hat u$. Wszystkie liczby zmiennoprzecinkowe w danych wejściowych są podane z dokładnością do $6$ cyfr znaczących.

Wyjście

Wynik wypisywany jest na standardowe wyjście.

Dla każdego zestawu danych wypisz liczbę $k$ oznaczającą liczbę boków wielokąta.

Przykład

Zobacz załączone pliki.

Uwagi

Poniżej przedstawiono wizualizacje odpowiednio dla zestawów danych nr $2, 4, 5, 8$.

Podzadania

Dla wszystkich punktów testowych $T=200$, $N=1000$, $3 \le n \le 30$.

Zadanie składa się z dziesięciu punktów testowych, każdy wart dziesięć punktów, testy nie są zgrupowane.

Punktacja

Dla każdego punktu testowego, jeśli popełnisz błąd w co najwyżej jednym zestawie danych, otrzymasz pełną liczbę punktów, w przeciwnym razie nie otrzymasz żadnych punktów.

Uwagi

Możesz potrzebować poniższych definicji matematycznych, jednak ich niezrozumienie nie wpływa na możliwość rozwiązania zadania:

Zmienna losowa $X$ podlegająca rozkładowi Gaussa ze średnią $\mu$ i odchyleniem standardowym $\sigma$, oznaczanemu jako $\mathcal N(\mu, \sigma^2)$, ma funkcję gęstości prawdopodobieństwa postaci $$f(x) = \frac{1}{\sqrt{2 \pi} \sigma} e^{-\frac{(x-\mu)^2}{2\sigma^2}}.$$ Dla ciągłej zmiennej losowej $X$ o funkcji gęstości prawdopodobieństwa $f(x)$ oraz liczb rzeczywistych $a < b$, prawdopodobieństwo, że wygenerowana liczba losowa $X$ znajdzie się w przedziale $(a,b)$, wynosi $$\Pr(X \in (a,b)) = \int_a^b f(x) dx.$$

Możesz potrzebować następujących właściwości problemu:

Cechą rozkładu Gaussa jest to, że jego gęstość maleje wykładniczo w miarę oddalania się od średniej, dlatego przy małym odchyleniu standardowym wartości zmiennej losowej z dużym prawdopodobieństwem są bliskie średniej. Na przykład w kontekście tego zadania, gdzie $\mu = 0$ oraz $\sigma = 0.01$, prawdopodobieństwo, że wartość bezwzględna wygenerowanej liczby losowej przekroczy $0.04$, wynosi około $6 \times 10^{-4}$, prawdopodobieństwo przekroczenia $0.05$ nie przekracza $6 \times 10^{-7}$, a prawdopodobieństwo przekroczenia $0.07$ nie przekracza $3 \times 10^{-12}$.