# 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 |r1r2|+|c1c2|=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 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 aa of nn pairs of adjacent squares. Find the size of the largest strong subarray of aa. An array pp is a subarray of an array qq if pp can be obtained from qq by deletion of several (possibly, zero or all) elements.
Input

The input consists of multiple test cases. The first line contains an integer tt (1t1001≤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 (1n1051≤n≤1052k5002≤k≤500kk 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,1ci,1ci,1ri,2ri,2, and ci,2ci,2 (1ri,1,ci,1,ri,2,ci,2k1≤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.

Output

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

Example
input

Copy
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

Note

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.