#pragma GCC optimize("O3,unroll-loops")
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <vector>
using namespace std;
#define sz(x) (int) (x).size()
#define i64 int64_t
#define all(x) (x).begin(), (x).end()

int log2_floor(unsigned long long i) {
    return i ? __builtin_clzll(1) - __builtin_clzll(i) : -1;
}

const int BUF_SZ = 1 << 15;
inline namespace Input {
    char buf[BUF_SZ];int pos;int len;
    char next_char() {
        if (pos == len) {pos = 0;
        len = (int)fread(buf, 1, BUF_SZ, stdin);
        if (!len) { return EOF; }}
        return buf[pos++];}
    i64 read_int() {
        i64 x;char ch;int sgn = 1;
        while (!isdigit(ch = next_char())) {
            if (ch == '-') { sgn *= -1; }}
        x = ch - '0';
        while (isdigit(ch = next_char())) { x = x * 10ll + (ch - '0'); }
        return x * sgn;}
}
inline namespace Output {
    char buf[BUF_SZ];int pos;
    void flush_out() {fwrite(buf, 1, pos, stdout);pos = 0;}
    void write_char(char c) {
        if (pos == BUF_SZ) { flush_out(); }
        buf[pos++] = c;}
    void write_int(i64 x) {
        static char num_buf[100];
        if (x < 0) {write_char('-');x *= -1;}
        int len = 0;
        for (; x >= 10; x /= 10) { num_buf[len++] = (char)('0' + (x % 10)); }
        write_char((char)('0' + x));
        while (len) { write_char(num_buf[--len]); }
        write_char('\n');}
    void init_output() { assert(atexit(flush_out) == 0); }
}

const int inf = 9;

struct sparsemin {
    vector<i64> a;
    int h;
    vector<vector<i64>> st;
    sparsemin() {}
    sparsemin(vector<i64>& arr) : a(arr), h(log2(a.size()) + 1), st(h + 1) {
        for (int i = 0; i < a.size(); i++) st[0].push_back(i);
        for (int i = 1; i <= h; i++)
            for (int j = 0; j + (1 << i) <= arr.size(); j++)
                st[i].push_back(a[st[i-1][j]] < a[st[i-1][j + (1 << (i-1))]] ? st[i-1][j] : st[i-1][j + (1 << (i-1))]);
    }
    int rmq(int l, int r) {
        int i = log2_floor(r - l + 1);
        return a[st[i][l]] < a[st[i][r - (1 << i) + 1]] ? st[i][l] : st[i][r - (1 << i) + 1];
    }
};

const int FAKE = 5e5+3;

vector<array<i64,2>> adj[FAKE];
int etour[4*FAKE],tin[FAKE],tot[FAKE];
i64 dtour[4*FAKE], dep[FAKE];
int tourp = 0;

void tinit(int n) {
	for (int i=0; i<n; i++) {
		adj[i].resize(0);
	}
	tourp = 0;
}

void add_edge(int u, int v, i64 w) {
    adj[u].push_back({v, w});
    adj[v].push_back({u, w});
}

void dfs(int v, int p, i64 d) {
	dep[v] = d;
	tin[v] = tourp;
	etour[tourp++] = v;
	for (const array<i64,2> &e : adj[v]) {
		if (e[0] == p) continue;
		dfs(e[0],v,d+e[1]);
		etour[tourp++] = v;
	}
	tot[v] = tourp;
	etour[tourp++] = v;
}

const int LG = 20;
int sparsetable[LG][4*FAKE];
void init_sparse() {
    dfs(0, 0, 0);
    for (int i=0; i<tourp; i++) {
        dtour[i] = dep[etour[i]];
    }
    for (int i=0; i<tourp; i++) {
        sparsetable[0][i] = i;
    }
    for (int i=1; i<=LG; i++) {
        for (int j=0; j + (1 << i) <= tourp; j++) {
            sparsetable[i][j] =
            (dtour[sparsetable[i-1][j]] < dtour[sparsetable[i-1][j + (1 << (i-1))]]
            ? sparsetable[i-1][j] : sparsetable[i-1][j + (1 << (i-1))]);
        }
    }
}

int rmq(int l, int r) {
	int i = log2_floor(r-l+1);
	return (dtour[sparsetable[i][l]] < dtour[sparsetable[i][r-(1<<i)+1]]
	? sparsetable[i][l] : sparsetable[i][r-(1<<i)+1]);
}
int lca(int u, int v) {
	return etour[rmq(min(tin[u],tin[v]),max(tot[u],tot[v]))];
}
i64 dist(int u, int v) {
    if (u == FAKE || v == FAKE) {return -69;}
	return dep[u] + dep[v] - 2*dep[lca(u,v)];
}

const int mxn = 5e5 + 5;

int n, q, c[mxn], qr[mxn][4], np;

void chmax(int &x, int &y, int x1, int y1) {
	if (dist(x1, y1) >= dist(x, y)) {
        x = x1;
        y = y1;
    }
}

const int MM=10;

int lo[MM*mxn],hi[MM*mxn],x[MM*mxn],y[MM*mxn],xd[MM*mxn],yd[MM*mxn],CXD[MM*mxn];
int lc[MM*mxn],rc[MM*mxn];

int nx = 0;
int create_node(int cxd) {
	CXD[nx]=cxd; x[nx]=FAKE; y[nx]=FAKE; lc[nx]=-1; rc[nx]=-1; xd[nx]=FAKE; yd[nx]=FAKE;
	return nx++;
}
int create_node(int l, int h, int cxd) {
	lo[nx]=l; hi[nx]=h;
	return create_node(cxd);
}
void pull(int v) {
	int &xv=x[v],&yv=y[v],&xdv=xd[v],&ydv=yd[v];
	xv=FAKE,yv=FAKE,xdv=FAKE,ydv=FAKE;
	if (lc[v]==-1 && rc[v]==-1) {return;}
	if (rc[v]==-1) {
		xv=x[lc[v]]; yv=y[lc[v]];
		if (CXD[v]) {xdv=xd[lc[v]],ydv=yd[lc[v]];}
		return;
	}
	if (lc[v]==-1) {
		xv=x[rc[v]]; yv=y[rc[v]];
		if (CXD[v]) {xdv=xd[rc[v]],ydv=yd[rc[v]];}
		return;
	}
	if (CXD[v]) {
		int lx=x[lc[v]],rx=x[rc[v]],ly=y[lc[v]],ry=y[rc[v]];
		int lxd=xd[lc[v]],rxd=xd[rc[v]],lyd=yd[lc[v]],ryd=yd[rc[v]];
		chmax(xdv,ydv,lx,rx); chmax(xdv,ydv,lx,ry); chmax(xdv,ydv,ly,rx);
		chmax(xdv,ydv,ly,ry); chmax(xdv,ydv,lxd,lyd); chmax(xdv,ydv,rxd,ryd);
		int tp=xdv; xv=tp; tp=ydv; yv=tp;
		if (c[lx]!=c[ly]) {chmax(xdv,ydv,lx,ly);}
		if (c[lx]!=c[ly]) {chmax(xdv,ydv,lx,ly);}
		chmax(xv,yv,lx,ly);
		chmax(xv,yv,rx,ry);
	} else {
		int lx=x[lc[v]],rx=x[rc[v]],ly=y[lc[v]],ry=y[rc[v]];
		chmax(xv,yv,lx,ly); chmax(xv,yv,lx,rx); chmax(xv,yv,lx,ry);
		chmax(xv,yv,ly,rx); chmax(xv,yv,ly,ry); chmax(xv,yv,rx,ry);
	}

}
void point_set(int v, int I, int X, int Y) {
	if (lo[v]==I && hi[v]==I) {x[v]=X,y[v]=Y;xd[v]=FAKE;yd[v]=FAKE; return;}
	if (I<=(lo[v]+hi[v])/2) {
		if (lc[v]==-1) {lc[v] = create_node(lo[v],(lo[v]+hi[v])/2,CXD[v]);}
		point_set(lc[v],I,X,Y);
	} else {
		if (rc[v]==-1) {rc[v] = create_node((lo[v]+hi[v])/2+1,hi[v],CXD[v]);}
		point_set(rc[v],I,X,Y);
	}
	pull(v);
}

int crt[mxn], trt;
vector<int> col[mxn];

void solve() {
	nx=0;
	for (int i=0; i<=q; i++) {col[i].resize(0);}
	q = read_int();
    c[0] = read_int();
    n = 0;
    col[c[0]].push_back(0);
    tinit(q + 1);
    np = 1;
    for (int i = 0; i < q; i++) {
        qr[i][0] = read_int();
        qr[i][1] = read_int();
        qr[i][2] = read_int();
        if (!qr[i][0]) {
            i64 d = read_int();
            add_edge(qr[i][1] - 1, np++, d);
            n++;
            qr[i][1] = np;
        }
        qr[i][1]--;
        col[qr[i][2]].push_back(qr[i][1]);
    }
    for (int i=0; i<=q; i++) {
    	sort(all(col[i]));
    	col[i].erase(unique(all(col[i])),col[i].end());
   	}

    init_sparse();

	for (int i = 0; i <= q; i++) {
        crt[i] = create_node(0, sz(col[i])+1,0);
    }
    trt = create_node(0, q + 1,1);
    point_set(crt[c[0]],0, 0, 0);
    point_set(trt, c[0], x[crt[c[0]]], y[crt[c[0]]]);
    for (int i = 0; i < q; i++) {
        int tr = qr[i][0], xx = qr[i][1], ci = qr[i][2];
        int pcx = c[xx];
        c[xx] = ci;
        if (tr) {
        	int xtv = lower_bound(all(col[pcx]),xx)-col[pcx].begin();
            point_set(crt[pcx], xtv, FAKE, FAKE);
            point_set(trt, pcx, x[crt[pcx]], y[crt[pcx]]);
        }
        int xtv = lower_bound(all(col[ci]),xx) - col[ci].begin();
        point_set(crt[ci],xtv, xx, xx);
        point_set(trt, ci, x[crt[ci]], y[crt[ci]]);
        write_int(max(dist(xd[trt], yd[trt]),0ll));
    }
}

signed main() {
    init_output();

    int t = read_int();
    while (t--) {
        solve();
    }

    return 0;
}