A14808. Not Splitting

There is a $k \times k$ grid, where $k$ is even. The square in row $r$ and column $c$ is denoted by $(r,c)$ . Two squares $(r_1, c_1)$ and $(r_2, c_2)$ are considered adjacent if $\lvert r_1 - r_2 \rvert + \lvert c_1 - c_2 \rvert = 1$ .

An array of adjacent pairs of squares is called strong if it is possible to cut the grid along grid lines into two connected, [congruent](https://en.wikipedia.org/wiki/Congruence_(geometry)) pieces so that each pair is part of the same piece. Two pieces are congruent if one can be matched with the other by translation, rotation, and reflection, or a combination of these.

 The picture above represents the first test case. Arrows indicate pairs of squares, and the thick black line represents the cut. You are given an array $a$ of $n$ pairs of adjacent squares. Find the size of the largest strong subsequence of $a$ . An array $p$ is a subsequence of an array $q$ if $p$ can be obtained from $q$ by deletion of several (possibly, zero or all) elements.

The input consists of multiple test cases. The first line contains an integer $t$ ( $1 \leq t \leq 100$ ) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two space-separated integers $n$ and $k$ ( $1 \leq n \leq 10^5$ ; $2 \leq k \leq 500$ , $k$ is even) — the length of $a$ and the size of the grid, respectively.

Then $n$ lines follow. The $i$ -th of these lines contains four space-separated integers $r_{i,1}$ , $c_{i,1}$ , $r_{i,2}$ , and $c_{i,2}$ ( $1 \leq r_{i,1}, c_{i,1}, r_{i,2}, c_{i,2} \leq k$ ) — the $i$ -th element of $a$ , represented by the row and column of the first square $(r_{i,1}, c_{i,1})$ and the row and column of the second square $(r_{i,2}, c_{i,2})$ . These squares are adjacent.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$ , and the sum of $k$ over all test cases does not exceed $500$ .

For each test case, output a single integer — the size of the largest strong subsequence of $a$ .

In the first test case, the array $a$ is not good, but if we take the subsequence $[a_1, a_2, a_3, a_4, a_5, a_6, a_8]$ , then the square can be split as shown in the statement.

In the second test case, we can take the subsequence consisting of the last four elements of $a$ and cut the square with a horizontal line through its center.