题目描述

有 $n$ 个彩色糖果在平面上。小奇想在平面上取一条水平的线段，并拾起它上方或下方的所有糖果。

求出最多能够拾起多少糖果，使得获得的糖果并不包含所有的颜色。

输入格式

包含多组测试数据，第一行输入一个正整数 $T$，表示测试数据组数。

接下来 $T$ 组测试数据，对于每组测试数据，第一行输入两个正整数 $n,k$ 分别表示点数和颜色数。

接下来 $n$ 行，每行描述一个点，前两个数 $x,y$ 描述点的位置，最后一个数 $z$ 描述点的颜色。

输出格式

对于每组数据在一行内输出一个非负整数 $ans$，表示答案。

样例输入

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

数据规模与约定

对于 $100\%$ 的数据，$1\le n,k \le 10^5$，$1 \le T \le 3$，$|x|,|y| \le 2^{30} - 1$，$1 \le z \le k$。

题目来源

By Hzwer