有一个 $$$k \times k$$$ 网格,其中 $$$k$$$ 是偶数。 $$$r$$$ 行和$$$c$$$ 列中的正方形由$$$(r,c)$$$ 表示。如果 $$$\lvert r_1 - r_2 \rvert + \lvert c_1 - c_2 \rvert = 1$$$,则两个正方形 $$$(r_1, c_1)$$$ 和 $$$(r_2, c_2)$$$ 被视为相邻。
如果可以沿着网格线将网格切割成两个相连的、全等的块,使得每对都是同一块的一部分,则相邻的成对的正方形阵列被称为强阵列。如果两个部分可以通过平移、旋转和反射或这些的组合与另一部分匹配,则两个部分是一致的。
上图代表第一个测试用例。箭头表示成对的方块,粗黑线表示切割。
给你一个数组 $$$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$$$) — $$$a$$$ 的第 $$$i$$$ 个元素,由第一个正方形 $$$(r_{i,1}, c_{i,1})$$$ 的行和列以及第二个正方形 $$$(r_{i,2}, c_{i,2})$$$ 的行和列表示。这些正方形是相邻的。
保证所有测试用例的$$$n$$$总和不超过$$$10^5$$$,所有测试用例的$$$k$$$总和不超过$$$500$$$。
输出
对于每个测试用例,输出一个整数 - $$$a$$$ 的最大强子序列的大小。
示例
输入 #1
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
输出 #1
7 4 1
注意
在第一个测试用例中,数组 $$$a$$$ 不好,但是如果我们取子序列 $$$[a_1, a_2, a_3, a_4, a_5, a_6, a_8]$$$,则可以如语句所示分割正方形。
在第二个测试用例中,我们可以采用 $$$a$$$ 的最后四个元素组成的子序列,并用穿过其中心的水平线切割正方形。