大盗亚森·罗平（Arsen Lupin）的目标是窃取埃尔文（Evil Erwin）的珠宝。埃尔文的店里陈列着 $n$ 颗珠宝。每颗宝石都有 $k$ 种不同颜色中的一种。展览规模很大，我们可以将其视为欧几里得平面，珠宝则是平面上不同的点。陈列柜由一些非常昂贵的警报器保护。

罗平发明了一种装置：一只巨大的机械手，可以在不触发任何警报的情况下抓取埃尔文的一些珠宝。该装置可以进行一次（且仅一次）抓取，抓取位于某条水平线段上或其下方的所有珠宝（见图）。罗平本可以轻易地用这种方式拿走所有珠宝，但他知道拿得越多，处理起来就越困难。他决定，最安全的方法是拿走一组不包含全部 $k$ 种颜色的珠宝。

计算罗平在不拿走所有颜色珠宝的前提下，使用一次装置最多能窃取多少颗珠宝。

机械手抓取了珠宝 1、2、4、5 和 6，小心地避开了黑色的珠宝

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是各测试用例的描述：

每个测试用例以两个整数 $n$ ($2 \leqslant n \leqslant 200\,000$) 和 $k$ ($2 \leqslant k \leqslant n$) 开头，分别表示珠宝的数量和不同颜色的数量。接下来的 $n$ 行表示珠宝的位置和颜色。第 $j$ 行包含三个空格分隔的整数 $x_j, y_j, c_j$ ($1 \leqslant x_j, y_j \leqslant 10^9$, $1 \leqslant c_j \leqslant k$)，表示第 $j$ 颗珠宝位于坐标 $(x_j, y_j)$ 处，颜色为 $c_j$。

你可以假设展览中至少存在每种颜色的一颗宝石。

输出格式

按输入中出现的顺序打印每个测试用例的答案。对于每个测试用例，打印一行，包含可能窃取的最大珠宝数量。

样例

输入 1

1
10 3
1 2 3
2 1 1
2 4 2
3 5 3
4 4 2
5 1 2
6 3 1
6 7 1
7 2 3
9 4 2

输出 1

5