Not Splitting

Description:

Input:

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$$$.

Output:

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

Sample Input:

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

Sample Output:

7
4
1

Note:

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.