E. Следы
ограничение по времени на тест
2.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы ходили по коридорам Закулисья, когда за одной из дверей раздался топот. Вы затаились и прислушались: судя по звукам, там было огромное чудовище, которое сделало ровно $$$k$$$ шагов (то есть оставило $$$k$$$ отпечатков каждой своей лапы).

В Закулисье чудовища ходят просто: на каждом шаге целиком сдвигаются на один и тот же неизвестный ненулевой целочисленный вектор. При этом они не поворачиваются и не меняют расположение лап относительно друг друга.

Пол комнаты разбит на квадратные клетки. После каждого шага каждая лапа оставляет след, занимающий ровно одну клетку. Следы могут перекрываться; клетка, на которую наступили несколько раз, выглядит так же, как клетка с одним следом.

Когда топот стих, вы заглянули в комнату и обнаружили ровно $$$n$$$ клеток со следами (никакого животного, естественно, уже не было).

Найдите минимально возможное количество лап у чудовища — или определите, что вам это померещилось и не было такого животного, которое оставило эти следы.

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

В первой строке задано целое число $$$t$$$ ($$$1\le t\le 2000$$$) — количество наборов входных данных. Далее описаны наборы входных данных.

В первой строке каждого набора заданы два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n,k \le 2000$$$) — количество клеток со следами и количество шагов чудовища.

В следующих $$$n$$$ строках заданы пары целых чисел $$$x_i,y_i$$$ ($$$-10^9\le x_i,y_i\le 10^9$$$) — координаты клеток со следами. Все пары в пределах одного набора различны. Клетки перечислены в произвольном порядке.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2000$$$.

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

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

Если ни одно чудовище не могло оставить заданные следы, выведите $$$-1$$$.

Пример
Входные данные
3
5 3
0 0
1 0
2 0
3 0
4 0
8 2
0 0
1 0
2 0
0 10
1 10
2 10
3 10
4 10
3 2
0 0
1 0
0 1
Выходные данные
2
5
-1
Примечание

В первом наборе примера у чудовища могли быть две лапы. Первая оставляет следы в клетках $$$(0,0)$$$, $$$(1,0)$$$ и $$$(2,0)$$$, а вторая — в клетках $$$(2,0)$$$, $$$(3,0)$$$ и $$$(4,0)$$$. Вектор каждого шага равен $$$(1,0)$$$.

Клетка $$$(2,0)$$$ отмечается дважды, но учитывается только один раз, поэтому всего получается пять клеток со следами. Одной лапы недостаточно: за три шага она оставила бы следы только в трёх клетках. Следовательно, ответ равен $$$2$$$.

Во втором наборе примера у чудовища могли быть пять лап. После первого шага они находятся в клетках $$$(0,0)$$$, $$$(1,0)$$$, $$$(0,10)$$$, $$$(2,10)$$$ и $$$(3,10)$$$. На втором шаге все лапы сдвигаются на вектор $$$(1,0)$$$. В результате следы занимают три клетки в строке $$$y=0$$$ и пять клеток в строке $$$y=10$$$.

Меньшего количества лап недостаточно. Сдвиг с ненулевой вертикальной компонентой невозможен: тогда после двух шагов в обеих строках было бы одинаковое количество отмеченных клеток. Значит, каждая лапа оставляет оба следа в одной строке. Для трёх клеток первой строки нужны хотя бы две лапы, а для пяти клеток второй — хотя бы три. Поэтому ответ равен $$$5$$$.

В третьем наборе примера получить заданные следы невозможно.