小智（Ash Ketchum）是一位立志捕捉世界上所有宝可梦的宝可梦训练家。幸运的是，他已经捕捉到了大部分宝可梦，现在他需要收集 $K$ 种不同的宝可梦来完成他的图鉴。

众所周知，小智生活在一个二维网格世界中。宝可梦出现在该网格的整数坐标上。在这个世界中，同一类型的宝可梦可能会出现多次。请记住，小智需要捕捉 $K$ 种不同的宝可梦，而不是 $K$ 只宝可梦。

小智决定通过从空中投掷一个巨大的正方形网来捕捉这些宝可梦。如果一只宝可梦位于网的边界内或其边缘上，则认为它被捕捉到了。小智想要找到一个包含这些宝可梦的正方形，使得正方形的每一条边都平行于 $x$ 轴或 $y$ 轴。

你能帮小智找到包含 $K$ 种不同宝可梦的正方形的最小边长吗？由于网必须始终具有正面积，因此正方形的边长必须为正数。

输入格式

你的程序将在一个或多个测试用例上进行测试。输入的第一行是一个整数 $T$，表示测试用例的数量（$1 \le T \le 100$）。

每个测试用例以一行包含两个空格分隔的整数开始：

• $N$：世界中宝可梦的数量（$2 \le N \le 1000$）
• $K$：宝可梦的种类数（$2 \le K \le 100$）

随后有 $N$ 行，每行包含三个空格分隔的整数：

• $X$：宝可梦的 $x$ 坐标（$-1,000,000 \le X \le 1,000,000$）
• $Y$：宝可梦的 $y$ 坐标（$-1,000,000 \le Y \le 1,000,000$）
• $Z$：宝可梦的类型（$1 \le Z \le K$）

输出格式

对于每个测试用例，输出一行，包含包含 $K$ 种不同宝可梦的正方形的最小边长。

样例

输入 1

2
5 2
0 0 1
0 1 1
0 2 1
2 0 2
2 1 2
3 3
0 0 1
1 1 2
2 2 3

输出 1

2
2