const int MAXN=5e5+5;
const LL MAXV=1LL<<62;
LL val[MAXN];
namespace Tree1{
	#define lch(k) node[node[k].lch]
	#define rch(k) node[node[k].rch]
	const double alpha=0.70;
	struct Node{
		int lch,rch,sz;
	}node[MAXN];
	int root,a[MAXN],n;
	bool isbad(int k){
		return alpha*node[k].sz<max(lch(k).sz,rch(k).sz);
	}
	void build(int &k,int lef,int rig,LL vl,LL vr){
		if(lef>rig) return k=0,void();
		int mid=lef+rig>>1;
		k=a[mid];
		val[k]=vl+vr>>1;
		if(lef==rig){
			node[k].lch=node[k].rch=0;
			node[k].sz=1;
			return;
		}
		build(node[k].lch,lef,mid-1,vl,val[k]-1);
		build(node[k].rch,mid+1,rig,val[k]+1,vr);
		node[k].sz=lch(k).sz+rch(k).sz+1;
	}
	void dfs(int k){
		if(!k)return;
		dfs(node[k].lch);
		a[++n]=k;
		dfs(node[k].rch);
	}
	void rebuild(int &k,LL vl,LL vr){
		n=0;
		dfs(k);
		build(k,1,n,vl,vr);
	}
	void check(int &k,int id,LL vl,LL vr){
		if(k){
			if(isbad(k))
			rebuild(k,vl,vr);
			else if(val[id]<val[k])
			check(node[k].lch,id,vl,val[k]-1);
			else
			check(node[k].rch,id,val[k]+1,vr);
		}
	}
	void Insert(int &k,int id){
		if(!k){
			k=id;
			node[k].lch=node[k].rch=0;
			node[k].sz=1;
			return;
		}
		node[k].sz++;
		if(val[id]<val[k])
		Insert(node[k].lch,id);
		else
		Insert(node[k].rch,id);
	}
	void Insert(int id){
		Insert(root,id);
		check(root,id,0,MAXV);
	}
	#undef lch
	#undef rch
}
namespace Tree2{
	struct Node{
		int r,sz,ch[2];
	}node[MAXN];
	#define lch(k) node[node[k].ch[0]]
	#define rch(k) node[node[k].ch[1]]
	void push_up(int k){
		node[k].sz=lch(k).sz+rch(k).sz+1;
	}
	void split(int k,int &k1,int &k2,LL v){
		if(!k) return k1=k2=0,void();
		if(val[k]<=v){
			k1=k;
			split(node[k].ch[1],node[k1].ch[1],k2,v);
			push_up(k1);
		}else{
			k2=k;
			split(node[k].ch[0],k1,node[k2].ch[0],v);
			push_up(k2);
		}
	}
	void merge(int &k,int k1,int k2){
		if(!k1||!k2)return k=k1|k2,void();
		if(node[k1].r>node[k2].r){
			k=k1;
			merge(node[k].ch[1],node[k1].ch[1],k2);
			push_up(k);
		}else{
			k=k2;
			merge(node[k].ch[0],k1,node[k2].ch[0]);
			push_up(k);
		}
	}
	void Insert(int &root,int id){
		node[id].r=rand();
		node[id].sz=1;
		node[id].ch[0]=node[id].ch[1]=0;
		int lef,rig;
		split(root,lef,rig,val[id]);
		merge(lef,lef,id);
		merge(root,lef,rig);
	}
	int rank(int root,LL v){
		int lef,rig,ans;
		split(root,lef,rig,v-1);
		ans=node[lef].sz+1;
		merge(root,lef,rig);
		return ans;
	}
	int query(int root,LL vl,LL vr){
		return rank(root,vr)-rank(root,vl);
	}
	#undef lch
	#undef rch
};
int root[MAXN],col[MAXN],hson[MAXN],dfr[MAXN];
void solve(){
	int n=1;
	col[1]=read_int();
	val[1]=0;
	val[0]=MAXV;
	Tree1::Insert(1);
	Tree2::Insert(root[col[1]],1);
	int m=read_int(),lastans=0;
	while(m--){
		int t=read_int()^lastans,u=read_int()^lastans,c=read_int()^lastans;
		if(t==1){
			int v=hson[u]?hson[u]:dfr[u];
			hson[u]=++n;
			col[n]=c;
			dfr[n]=v;
			val[n]=val[u]+val[v]>>1;
			Tree1::Insert(n);
			Tree2::Insert(root[c],n);
		}
		else{
			lastans=Tree2::query(root[c],val[u],val[dfr[u]]);
			enter(lastans);
		}
	}
	Tree1::root=0;
	_rep(i,1,n){
		root[col[i]]=0;
		hson[i]=dfr[i]=0;
	}
}
int main()
{
	int T=read_int();
	while(T--)
	solve();
	return 0;
}