Сяо А и Сяо S — товарищи по команде ACM. У Сяо А отличное зрение, и он часто замечает странные закономерности в данных.

Во время одной из тренировок Сяо S нарисовал на бумаге круг. Сяо А взглянул на него и сказал: «Это же правильный 17-угольник!». Затем он достал множество изображений правильных многоугольников и предложил Сяо S понаблюдать за ними. Но Сяо S не имел об этом ни малейшего представления, поэтому он попросил вас помочь ему с идентификацией.

Конкретнее, при заданном максимальном количестве сторон многоугольника $n$, Сяо А генерирует $N$ точек на плоскости следующим образом:

• Сначала выбирается точка $(x, y)$ в качестве центра. Эта точка может быть зафиксирована в $(0, 0)$ или выбрана равномерно из области $[-1, 1] \times [-1, 1]$.
• Случайным образом выбирается целое число $k$ из диапазона $[\max(3, n-5), n]$.
• Рассматривается круг с центром в $(x, y)$ и радиусом $1$. Равномерно случайным образом выбирается вписанный в этот круг правильный $k$-угольник.
• Процесс повторяется $N$ раз: каждый раз равномерно случайным образом выбирается точка $u$ на границе правильного $k$-угольника, и в данные добавляется $\hat u = u + \mathcal N$. Здесь $\mathcal N$ — случайный шум, координаты которого по обеим осям независимо подчиняются нормальному распределению с математическим ожиданием $0$ и стандартным отклонением $0.01$.
• Все вышеперечисленные случайные процессы независимы.

Вам необходимо по этим $N$ точкам восстановить количество сторон многоугольника $k$.

Входные данные

Данные считываются из стандартного ввода.

В задаче содержится несколько наборов входных данных. В первой строке вводится целое число $T$, количество наборов данных.

Для каждого набора данных в первой строке вводятся два целых числа $N$ и $n$, обозначающие количество точек и максимально возможное число сторон многоугольника. Далее следуют $N$ строк, каждая из которых содержит два числа с плавающей запятой $\hat u_x, \hat u_y$, представляющие координаты точки $\hat u$. Все числа с плавающей запятой во входных данных представлены с $6$ значащими цифрами.

Выходные данные

Результат выводится в стандартный вывод.

Для каждого набора данных выведите число $k$, обозначающее количество сторон многоугольника.

Примеры

См. прилагаемые файлы.

Примечание

Ниже представлены визуализации для 2-го, 4-го, 5-го и 8-го наборов данных из примера.

Подзадачи

Для всех тестовых случаев $T=200$, $N=1000$, $3 \le n \le 30$.

Всего в задаче десять тестовых случаев, каждый оценивается в 10 баллов, тесты не сгруппированы.

Оценивание

Для каждого тестового случая, если вы ошиблись не более чем в одном наборе данных, вы получаете полный балл за этот случай, в противном случае — 0 баллов.

Примечание

Вам могут понадобиться следующие математические определения, однако их непонимание не препятствует решению задачи:

Случайная величина $X$, подчиняющаяся нормальному распределению $\mathcal N(\mu, \sigma^2)$ с математическим ожиданием $\mu$ и стандартным отклонением $\sigma$, имеет функцию плотности вероятности $$f(x) = \frac{1}{\sqrt{2 \pi} \sigma} e^{-\frac{(x-\mu)^2}{2\sigma^2}}.$$ Для непрерывной случайной величины $X$ с функцией плотности вероятности $f(x)$ и вещественных чисел $a < b$, вероятность того, что случайная величина $X$ примет значение в интервале $(a, b)$, равна $$\Pr(X \in (a,b)) = \int_a^b f(x) dx.$$

Вам могут быть полезны следующие свойства:

Характеристика нормального распределения: его плотность убывает экспоненциально при удалении от среднего значения, поэтому при малом стандартном отклонении значения случайной величины с высокой вероятностью близки к среднему. Например, в условиях данной задачи $\mu = 0$, $\sigma = 0.01$, вероятность того, что абсолютное значение сгенерированного случайного числа превысит $0.04$, составляет примерно $6 \times 10^{-4}$, вероятность превышения $0.05$ не превышает $6 \times 10^{-7}$, а вероятность превышения $0.07$ не превышает $3 \times 10^{-12}$.