#include <algorithm>
#include <iostream>
#include <vector>

const int M = 5e5 + 10;
const int K = 20;
std::vector<std::pair<int, int>> adj[M];
long long ST[K][2 * M], dis[M];
int op[M], x[M], y[M], c[M], d[M], p[M], cnt[M], color[M], pos[M];
int depth[M], eulern[M], Log2[2 * M];
int dfs_clock;

template<class T, class C> struct ZKW_Tree {
    size_t n{};
    std::vector<T> tree;
    ZKW_Tree() = default;
    void init(size_t n, T t) {
        this->n = 1;
        while (this->n < n + 2) {
            this->n <<= 1;
        }
        tree = std::vector<T>(this->n << 1, t);
    }
    void update(int i, T x) {
        for (tree[i += n] = x; i > 1; i >>= 1) {
            auto original = tree[i >> 1];
            tree[i >> 1] = C()(tree[i], tree[i ^ 1]);
            if (tree[i >> 1] == original) {
                break;
            }
        }
    }
    T top() {
        return tree[1];
    }
};

void dfs(int u, int fa) {
    ++dfs_clock;
    ST[0][dfs_clock] = dis[u];
    eulern[u] = dfs_clock;
    for (auto [v, w]: adj[u]) {
        dis[v] = dis[u] + w;
        depth[v] = depth[u] + 1;
        dfs(v, u);
        ++dfs_clock;
        ST[0][dfs_clock] = dis[u];
    }
}

void ST_init() {
    for (int k = 1; k < K; ++k) {
        for (int i = 1; i <= dfs_clock - (1 << k) + 1; ++i) {
            ST[k][i] = std::min(ST[k - 1][i], ST[k - 1][i + (1 << (k - 1))]);
        }
    }
}

long long distance(int u, int v) {
    int x = eulern[u];
    int y = eulern[v];
    if (x > y) {
        std::swap(x, y);
    }
    int k = Log2[y - x + 1];
    return dis[u] + dis[v] - 2 * std::min(ST[k][x], ST[k][y - (1 << k) + 1]);
}
struct merge {
    std::pair<int, int> operator()(std::pair<int, int> p1, std::pair<int, int> p2) {
        if (p1.first == -1) {
            return p2;
        }
        if (p2.first == -1) {
            return p1;
        }
        int nodes[4] = {p1.first, p1.second, p2.first, p2.second};
        std::tuple<long long, int, int> path(-1, -1, -1);
        for (int i = 0; i < 4; ++i) {
            for (int j = i + 1; j < 4; ++j) {
                path = std::max(path, std::make_tuple(distance(nodes[i], nodes[j]), nodes[i], nodes[j]));
            }
        }
        return {std::get<1>(path), std::get<2>(path)};
    }
};
struct merge2 {
    std::pair<std::pair<int, int>, int>
    operator()(std::pair<std::pair<int, int>, int> p1, std::pair<std::pair<int, int>, int> p2) {
        if (p1.first.first == -1) {
            return p2;
        }
        if (p2.first.first == -1) {
            return p1;
        }
        std::pair<std::pair<int, int>, int> ret;
        ret.first = merge()(p1.first, p2.first);
        if (color[ret.first.first] != color[ret.first.second]) {
            ret.second = ret.first.first;
            return ret;
        }
        int nodes[6] = {p1.first.first, p1.first.second, p2.first.first, p2.first.second};
        int m = 4;
        if (p1.second != -1) {
            nodes[m++] = p1.second;
        }
        if (p2.second != -1) {
            nodes[m++] = p2.second;
        }
        std::tuple<long long, int, int> path(-1, -1, -1);
        for (int i = 0; i < m; ++i) {
            for (int j = i + 1; j < m; ++j) {
                if (color[nodes[i]] != color[nodes[j]]) {
                    path = std::max(path, std::make_tuple(distance(nodes[i], nodes[j]), nodes[i], nodes[j]));
                }
            }
        }
        if (std::get<0>(path) == -1) {
            ret.second = -1;
        } else {
            int u = std::get<1>(path), v = std::get<2>(path);
            ret.second = color[u] == color[ret.first.first] ? v : u;
        }
        return ret;
    }
};


ZKW_Tree<std::pair<int, int>, merge> F[M];
ZKW_Tree<std::pair<std::pair<int, int>, int>, merge2> G;

void updateU(int u, std::pair<int, int> p) {
    F[color[u]].update(pos[u], p);
    G.update(color[u], {F[color[u]].top(), -1});
}

int main() {
    for (int i = 2; i < M * 2; ++i) {
        Log2[i] = Log2[i >> 1] + 1;
    }
    int _;
    for (scanf("%d", &_); _ != 0; --_) {
        int q, n = 1;
        scanf("%d%d", &q, &color[1]);
        for (int i = 1; i <= q; ++i) {
            cnt[i] = 0;
            adj[i].clear();
        }
        ++cnt[color[1]];
        p[0] = cnt[color[1]];
        for (int i = 1; i <= q; ++i) {
            scanf("%d", &op[i]);
            if (op[i] == 0) {
                scanf("%d%d%d", &x[i], &c[i], &d[i]);
                ++n;
                adj[x[i]].emplace_back(n, d[i]);
                ++cnt[c[i]];
                p[i] = cnt[c[i]];
                y[i] = n;
            } else {
                scanf("%d%d", &x[i], &c[i]);
                ++cnt[c[i]];
                p[i] = cnt[c[i]];
            }
        }
        dfs_clock = 0;
        dfs(1, -1);
        ST_init();
        G.init(q, {{-1, -1}, -1});
        for (int i = 1; i <= q; ++i) {
            F[i].init(cnt[i], {-1, -1});
        }
        pos[1] = p[0];
        updateU(1, {1, 1});
        for (int i = 1; i <= q; ++i) {
            if (op[i] == 0) {
                int u = y[i];
                color[u] = c[i];
                pos[u] = p[i];
                updateU(u, {u, u});
            } else {
                int u = x[i];
                updateU(u, {-1, -1});
                color[u] = c[i];
                pos[u] = p[i];
                updateU(u, {u, u});
            }
            auto top = G.top();
            if (top.second == -1) {
                puts("0");
            } else {
                long long res = std::max(distance(top.first.first, top.second), distance(top.first.second, top.second));
                printf("%lld\n", res);
            }
        }
    }
    return 0;
}