Ограбление ювелирного магазина
Арсен Люпен, мастер-взломщик, планирует украсть драгоценности у Злого Эрвина. В магазине Эрвина выставлено 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.
Вы можете предположить, что на выставке есть хотя бы один камень каждого цвета.
Выходные данные
Выведите ответы на тесты в порядке их появления во входных данных. Для каждого теста выведите одну строку, содержащую максимальное возможное количество украденных драгоценностей.