F. Не разрезать
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть квадрат $$$k \times k$$$, причем $$$k$$$ четно. Клетка в строке $$$r$$$ и столбце $$$c$$$ обозначается $$$(r,c)$$$. Две клетки $$$(r_1, c_1)$$$ и $$$(r_2, c_2)$$$ называются соседними, если $$$\lvert r_1 - r_2 \rvert + \lvert c_1 - c_2 \rvert = 1$$$.

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

Рисунок выше демонстрирует первый пример. Стрелки показывают пары клеток, а жирная линия показывает разрез на две части.

Вам дан массив $$$a$$$ из $$$n$$$ пар соседних клеток. Найдите размер наибольшей прочной подпоследовательности $$$a$$$. Массив $$$p$$$ является подпоследовательностью $$$q$$$, если $$$p$$$ может быть получен из $$$q$$$ удалением нескольких (возможно, ни одного или всех) элементов.

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

Во входных данных находятся несколько наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \leq t \leq 100$$$) — количество наборов входных данных. Далее следуют наборы входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \leq n \leq 10^5$$$; $$$2 \leq k \leq 500$$$, $$$k$$$ четно) — размер $$$a$$$ и размер квадрата, соответственно.

Далее следуют $$$n$$$ строк. $$$i$$$-я из этих строк содержит четыре целых числа $$$r_{i,1}$$$, $$$c_{i,1}$$$, $$$r_{i,2}$$$ и $$$c_{i,2}$$$ ($$$1 \leq r_{i,1}, c_{i,1}, r_{i,2}, c_{i,2} \leq k$$$) — $$$i$$$-й элемент $$$a$$$, где $$$(r_{i,1}, c_{i,1})$$$ — строка и столбец первой клетки, а $$$(r_{i,2}, c_{i,2})$$$ — строка и столбец второй. Эти квадраты соседние.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$, и что сумма значений $$$k$$$ по всем наборам входных данных не превосходит $$$500$$$.

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

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

Пример
Входные данные
3
8 4
1 2 1 3
2 2 2 3
3 2 3 3
4 2 4 3
1 4 2 4
2 1 3 1
2 2 3 2
4 1 4 2
7 2
1 1 1 2
2 1 2 2
1 1 1 2
1 1 2 1
1 2 2 2
1 1 2 1
1 2 2 2
1 6
3 3 3 4
Выходные данные
7
4
1
Примечание

В первом примере $$$a$$$ не является прочным, но подпоследовательность $$$[a_1, a_2, a_3, a_4, a_5, a_6, a_8]$$$ является, т. к. квадрат может быть разрезан способом, показанным в условии.

Во втором примере подпоследовательность из четырех последних элементов $$$a$$$ является прочным, т. к. квадрат можно разрезать с помощью горизонтальной прямой через центр.