题目描述

有 $\red{N }$个彩色糖果在平面上。小奇想在平面上取一条水平的线段,并拾起它上方或下方的所有糖果。求出最多能够拾起多少糖果,使得获得的糖果并不包含所有的颜色。

输入格式

包含多组测试数据,第一行输入一个正整数 $\red{T }$表示测试数据组数。

接下来 $\red{T }$组测试数据,对于每组测试数据,第一行输入两个正整数 $\red{N}$、$\red{K,}$分别表示点数和颜色数。

接下来 $\red{N }$行,每行描述一个点,前两个数 $\red{x, y (|x|, |y| ≤}$ $\red{2^{30} - 1) }$描述点的位置,最后一个数 $\red{z (1 ≤}$ $\red{z ≤}$ $\red{k) }$描述点的颜色。

输出格式

对于每组数据在一行内输出一个非负整数 $\red{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

提示

对于 $\red{30\% }$的数据,$\red{N ≤}$ $\red{100}$;

对于 $\red{60\% }$的数据,$\red{N ≤}$ $\red{5000}$;

对于 $\red{100\% }$的数据,$\red{N ≤}$ $\red{100000,K ≤}$ $\red{100000,T ≤}$ $\red{3}$。