Jewel Heist

Arsène Lupin, the master thief, wants to steal the jewels of the villain Erwin. Erwin has $n$ jewels on display in his shop. Every jewel has one of $k$ distinct colors. The showroom is so large that we treat it as the Euclidean plane, with the jewels being distinct points. The display is guarded by some rather expensive alarms.

Lupin has invented a device: a large robotic hand that can grab some of Erwin's jewels without triggering any alarm. The hand can make exactly one grab. Lupin picks a horizontal segment, and the hand takes every jewel whose $x$-coordinate lies within the segment's horizontal span and whose $y$-coordinate is at most the segment's height — that is, every jewel lying on the segment or somewhere below it (see the figure).

Lupin could easily take all the jewels this way, but he knows that the more he takes, the harder they will be to fence. He decides that the safest haul is a set of jewels that does not contain all $k$ colors.

The robotic hand grabs jewels 1, 2, 4, 5 and 6, carefully leaving out the black ones.

Determine how many jewels Lupin can steal with a single grab of his device, without ending up with a jewel of every color.

The first line contains the number of test cases $T$. The test cases follow.

Each test case begins with a line containing two integers $n$ and $k$ ($2 \le n \le 200\,000$, $2 \le k \le n$): the number of jewels and the number of distinct colors. Each of the next $n$ lines contains three integers $x_j$, $y_j$, $c_j$ ($1 \le x_j, y_j \le 10^9$, $1 \le c_j \le k$), meaning that jewel $j$ lies at coordinates $(x_j, y_j)$ and has color $c_j$.

You may assume that every color from $1$ to $k$ appears on at least one jewel.

For each test case, print a single line containing the maximum possible number of stolen jewels such that the stolen set does not contain all $k$ colors.