Пограбування ювелірного магазину
Арсен Люпен, відомий майстерний злодій, планує викрасти коштовності у Злого Ервіна. Ервін має n коштовностей, виставлених у своєму магазині. Кожна коштовність має один з k різних кольорів. Вітрина настільки велика, що її можна уявити як евклідову площину, де коштовності розташовані як окремі точки. Вітрина захищена дорогими сигналізаціями.
Люпен розробив пристрій: велику, роботизовану руку, яка може захопити деякі з коштовностей Ервіна, не активуючи сигналізацію. Рука може здійснити одне (і лише одне) захоплення, забираючи всі коштовності, що знаходяться на певному горизонтальному рівні або нижче нього (див. малюнок). Люпен міг би легко забрати всі коштовності таким чином, але він знає, що чим більше він візьме, тим важче буде їх приховати. Тому він вирішив, що найкраще взяти набір коштовностей, який не містить усіх k кольорів.
Малюнок 1. Роботизована рука захоплює коштовності 1, 2, 4, 5 і 6, обережно уникаючи чорних
Визначте, скільки коштовностей Люпен може вкрасти за одне захоплення свого пристрою, не беручи коштовності кожного кольору.
Вхідні дані
Перша строка вхідних даних містить кількість тестових випадків T. Опис тестових випадків подано далі:
Кожен тестовий випадок починається з двох цілих чисел n (2 ≤ n ≤ 200000) і k (2 ≤ k ≤ n), що позначають кількість коштовностей і кількість різних кольорів. Наступні n рядків описують позиції та кольори коштовностей. j-й рядок містить три цілі числа, розділені пробілами: x_j, y_j, c_j (1 ≤ x_j, y_j ≤ 10^9, 1 ≤ c_j ≤ k), що означає, що j-та коштовність знаходиться на координатах (x_j, y_j) і має колір c_j.
Ви можете припустити, що на виставці є принаймні один камінь кожного кольору.
Вихідні дані
Виведіть відповіді на тестові випадки у порядку, в якому вони з'являються у вхідних даних. Для кожного тестового випадку виведіть один рядок, що містить максимальну можливу кількість вкрадених коштовностей.