#include<bits/stdc++.h>
using namespace std;

void Read(int &val) {
    val = 0; char c;
    do { c = getchar(); } while (!isdigit(c));
    while (isdigit(c)) { val = val * 10 + c - '0'; c = getchar(); }
}

struct data {
    int X, Y, color;
    data() {}; data(int X, int Y, int color) : X(X), Y(Y), color(color) {};
    bool operator < (const data &a) const {
        return Y < a.Y || (Y == a.Y && X < a.X);
    }
};

const int N = 1e5 + 4, oo = 1e9 + 7;
int T, n, k;
data a[N];

vector<int> rar;

void compress() {
    rar.clear();
    for (int i = 1; i <= n; ++i) rar.push_back(a[i].X);
    sort(rar.begin(), rar.end());
    rar.resize(unique(rar.begin(), rar.end()) - rar.begin());
    for (int i = 1; i <= n; ++i) a[i].X = lower_bound(rar.begin(), rar.end(), a[i].X) - rar.begin() + 1;

    rar.clear();
    for (int i = 1; i <= n; ++i) rar.push_back(a[i].Y);
    sort(rar.begin(), rar.end());
    rar.resize(unique(rar.begin(), rar.end()) - rar.begin());
    for (int i = 1; i <= n; ++i) a[i].Y = lower_bound(rar.begin(), rar.end(), a[i].Y) - rar.begin() + 1;
}

set<int> Set[N];

struct Binary_Indexed_Tree {
    int node[N];

    void clear(int n) { for (int i = 0; i <= n; ++i) node[i] = 0; }

    int get(int pos) {
        int ans = 0;
        for (int i = pos; i > 0; i -= i & (-i)) ans += node[i];
        return ans;
    }

    void update(int pos, int val, int n) {
        for (int i = pos; i <= n && i > 0; i += i & (-i)) node[i] += val;
    }
} BIT;

int res;

void process() {
    sort(a+1, a+n+1); res = 0;

    for (int i = 1; i <= k; ++i) {
        Set[i].clear();
        Set[i].insert(0); Set[i].insert(n+1);
    }
    BIT.clear(n);

    for (int l = 1; l <= n; ++l) {
        int r = l;
        while (r <= n && a[r].Y == a[l].Y) ++r; --r;

        for (int i = l; i <= r; ++i) {
            int col = a[i].color;

            auto itR = Set[col].lower_bound(a[i].X);
            auto itL = Set[col].upper_bound(a[i].Y); itL--;

            int L = (*itL), R = (*itR);
            if (L == a[i].X || R == a[i].X) continue;
            res = max( res, BIT.get(R-1) - BIT.get(L) );
        }

        for (int i = l; i <= r; ++i) {
            BIT.update(a[i].X, 1, n);
            Set[a[i].color].insert(a[i].X);
        }

        l = r;
    }
}

bool cmp(data a, data b) { return a.X < b.X || (a.X == b.X && a.Y < b.Y); }

int save[N];

void Special() {
    sort(a+1, a+n+1, cmp);

    for (int i = 1; i <= k; ++i) save[i] = 0;

    for (int i = 1; i <= n; ++i) {
        int Prev = save[a[i].color];

        int tmp = BIT.get(a[i].X-1) - BIT.get(a[Prev].X);
        res = max(res, tmp);

        save[a[i].color] = i;
    }

    for (int i = 1; i <= k; ++i) {
        int Prev = save[i];

        int tmp = BIT.get(n) - BIT.get(a[Prev].X);
        res = max(res, tmp);
    }
}

bool vis[N];

void sol() {
    compress();

        for (int i = 1; i <= k; ++i) vis[i] = false;
        for (int i = 1; i <= n; ++i) vis[a[i].color] = true;
        for (int i = 1; i <= k; ++i) if (!vis[i]) { cout << n << '\n'; return; }

    process();

    Special();

    cout << res << '\n';
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    freopen("heist.inp", "r", stdin);
    freopen("heist.out", "w", stdout);

    Read(T);
    while (T--) {
        Read(n); Read(k);
        for (int i = 1; i <= n; ++i) {
            Read(a[i].X); Read(a[i].Y); Read(a[i].color);
        }

        sol();
    }

    return 0;
}