Table of Contents

## Not Splitting solution codeforces

**Not Splitting solution codeforces** – There is a k×kk×k grid, where kk is even. The square in row rr and column cc is denoted by (r,c)(r,c). Two squares (r1,c1)(r1,c1) and (r2,c2)(r2,c2) are considered adjacent if |r1−r2|+|c1−c2|=1|r1−r2|+|c1−c2|=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 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 input consists of multiple test cases. The first line contains an integer tt (1≤t≤1001≤t≤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 nn and kk (1≤n≤1051≤n≤105; 2≤k≤5002≤k≤500, kk is even) — the length of aa and the size of the grid, respectively.

## Not Splitting solution codeforces

Then nn lines follow. The ii-th of these lines contains four space-separated integers ri,1ri,1, ci,1ci,1, ri,2ri,2, and ci,2ci,2 (1≤ri,1,ci,1,ri,2,ci,2≤k1≤ri,1,ci,1,ri,2,ci,2≤k) — the ii-th element of aa, represented by the row and column of the first square (ri,1,ci,1)(ri,1,ci,1) and the row and column of the second square (ri,2,ci,2)(ri,2,ci,2). These squares are adjacent.

It is guaranteed that the sum of nn over all test cases does not exceed 105105, and the sum of kk over all test cases does not exceed 500500.

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

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

## output Not Splitting solution codeforces

7 4 1

In the first test case, the array aa is not good, but if we take the subarray [a1,a2,a3,a4,a5,a6,a8][a1,a2,a3,a4,a5,a6,a8], then the square can be split as shown in the statement.

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