SP8104 KFRIENDS - Friendly Knights

 古拉姆城是一个以骑士文化著称的城市，其形状与一块国际象棋棋盘相同。城市中有些格子上驻扎着骑士。由于草料短缺（全球变暖的缘故），每对邻近的骑士之间发生了争执。如果骑士 A 在一步内可以到达骑士 B，则称骑士 A 是骑士 B 的邻居（见注释了解详情）。 为了化解矛盾，联合国计划举办“友谊节”，为骑士们分发友谊项链。每对邻居骑士会交换颜色相同的项链并佩戴，以此象征和睦。为了增添多样性，联合国希望每位骑士佩戴的项链颜色都各不相同。联合国对于某种颜色的项链可以不限数量地生产，但你能帮他们算出至少需要多少种颜色吗？ **注释：** 国际象棋中的规则，位于 (x, y) 格子的骑士可以一步移动到 (x+2, y+1)、(x+2, y-1)、(x+1, y+2)、(x+1, y-2)、(x-2, y+1)、(x-2, y-1)、(x-1, y+2) 或 (x-1, y-2)。

第一行输入一个整数 T（约 10），表示测试用例的数量。对每个测试用例，第一行输入一个整数 N（0 ≤ N ≤ 10000），表示城市中骑士的数量。接下来的 N 行，每行有两个整数 X 和 Y，分别表示骑士所在的行列编号（1 ≤ X, Y ≤ 100）。没有两个骑士会站在同一个格子上。

对于每个测试用例，输出所需的最少颜色数，每个结果占一行。

- 骑士数量 0 ≤ N ≤ 10000 - 行和列编号 1 ≤ X, Y ≤ 100 **本翻译由 AI 自动生成**