Arsen Lupin, the master thief, aims to steal Evil Erwin’s jewels. Erwin has \textbf{n} jewels on display in his store. Every precious stone is of one of \textbf{k} distinct colors. The exposition is so large that we can treat it as the Euclidean plane with the jewels being distinct points. The display is secured by some quite expensive alarms. Lupin has invented a device: a big, robotic hand that can grab some of the Erwin’s jewels without triggering any of the alarms. The hand can make one (and only one) grab, taking all the jewels lying on some horizontal segment or below it (see the picture). Lupin could easily take all the jewels this way, but he knows that the more he takes, the harder it will be to get rid of them. He decided that the safest way is to take a set of jewels that does not contain all the \textbf{k} colors. \includegraphics{https://static.e-olymp.com/content/a0/a00641c6fad467a01f4aa122f37f53ddd41b1555.jpg} Picture 1. The robotic hand grabs jewels 1, 2, 4, 5 and 6, carefully omitting the black ones Compute how many jewels Lupin can steal with one grab of his device, without taking jewels in every color. \InputFile The first line of the input contains the number of test cases \textbf{T}. The descriptions of the test cases follow: Each test case starts with two integers \textbf{n} (\textbf{2} ≤ \textbf{n} ≤ \textbf{200000}) and \textbf{k} (\textbf{2} ≤ \textbf{k} ≤ \textbf{n}) denoting the number of jewels and the number of distinct colors. The next \textbf{n} lines denote the jewels’ positions and colors. The \textbf{j}-th line contains three space-separated integers\textbf{x_j}, \textbf{y_j}, \textbf{c_j} (\textbf{1} ≤ \textbf{x_j}, \textbf{y_j} ≤ \textbf{10^9}, \textbf{1} ≤ \textbf{c_j} ≤ \textbf{k}) meaning that the \textbf{j}-th jewel lies at coordinates (\textbf{x_j}, \textbf{y_j}) and has color \textbf{c_j}. You may assume that there is at least one stone of every color at the exposition. \OutputFile Print the answers to the test cases in the orderin which they appear in the input. For each test case print a single line containing the maximum possible number of stolen jewels.