说明

大盗 Arsen Lupin 的目标是偷走 Evil Erwin 的宝石。Erwin 的商店里陈列着 $n$ 颗宝石。每一颗宝石都有 $k$ 种不同颜色中的一种。展区非常大，我们可以将其视为欧几里得平面，宝石就是平面上的不同点。陈列柜由一些相当昂贵的警报器保护着。

Lupin 发明了一个装置：一只巨大的机械手，可以在不触发任何警报的情况下抓取 Erwin 的一些宝石。这只手只能进行一次抓取，抓取位于某条水平线段上及其下方的所有宝石（见图）。Lupin 本可以轻易地用这种方式拿走所有宝石，但他知道拿得越多，就越难脱手。他决定最安全的方式是拿取一组不包含全部 $k$ 种颜色的宝石。

计算 Lupin 用他的装置一次抓取最多能偷走多少颗宝石，且不能拿走所有颜色的宝石。

输入格式

第一行包含测试用例数量 $T$。随后是每个测试用例的描述：

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

你可以假设每种颜色至少有一颗宝石在展区中。

输出格式

按照输入中出现的顺序输出每个测试用例的答案。对于每个测试用例，输出一行，包含可能偷走的宝石的最大数量。

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

5

提示

翻译由 DeepSeek 完成