보석 강탈

괴도 아르센 뤼팽이 악당 어윈의 보석을 훔치려 한다. 어윈의 상점에는 $n$개의 보석이 전시되어 있고, 각 보석은 $k$가지 색 중 하나를 가진다. 전시장이 매우 넓어 유클리드 평면으로 볼 수 있으며, 보석들은 서로 다른 점으로 나타낸다. 전시장은 상당히 값비싼 경보기로 보호되고 있다.

뤼팽은 장치 하나를 발명했다. 경보를 울리지 않고 어윈의 보석 일부를 집어 올릴 수 있는 커다란 로봇 팔이다. 이 팔은 정확히 한 번만 집을 수 있다. 뤼팽이 수평 선분 하나를 정하면, 팔은 $x$좌표가 그 선분의 가로 범위 안에 있고 $y$좌표가 그 선분의 높이 이하인 모든 보석, 즉 선분 위에 있거나 그 아래에 있는 모든 보석을 가져간다(그림 참고).

이렇게 하면 모든 보석을 가져갈 수도 있지만, 많이 가져갈수록 처분하기 어렵다는 것을 뤼팽은 알고 있다. 그래서 그는 $k$가지 색을 모두 포함하지 않는 보석 집합을 가져가는 것이 가장 안전하다고 판단했다.

로봇 팔이 검은색 보석을 조심스럽게 빼고 1, 2, 4, 5, 6번 보석을 집는다.

색을 모두 갖추지 않으면서 장치를 한 번 집어 뤼팽이 훔칠 수 있는 보석의 최대 개수를 구하여라.

첫 번째 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 각 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 두 정수 $n$과 $k$ ($2 \le n \le 200,000$, $2 \le k \le n$)가 주어지며, 각각 보석의 수와 서로 다른 색의 수를 의미한다. 이어지는 $n$개의 줄에는 각각 세 정수 $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$부터 $k$까지의 모든 색은 적어도 하나의 보석에 나타난다고 가정해도 된다.

각 테스트 케이스마다, 훔친 보석 집합이 $k$가지 색을 모두 포함하지 않도록 하면서 훔칠 수 있는 보석의 최대 개수를 한 줄에 출력한다.