#include<bits/stdc++.h> #define fi first #define se second #define pii pair<int,int> using namespace std; const int N=1e5+10; int T,n,m,a[N],in[N],vis[N]; vector<int> ve[N]; queue<int> qu; struct Q{ int x,c,y,d; void read(){ scanf("%d%d%d%d",&x,&c,&y,&d); if(c>d) swap(x,y),swap(c,d); } bool operator <(const Q &u)const{ if(c==u.c) return d<u.d; return c<u.c; } }q[N]; void bfs(){ while(!qu.empty()){ int x=qu.front(); qu.pop(); if(vis[x]) continue; vis[x]=1; for(int i=0;i<ve[x].size();i++){ int y=ve[x][i]; if(!vis[y]){ a[y]=2; qu.push(y); } } } } void solve(){ scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) q[i].read(); sort(q+1,q+1+m); int l,r; for(l=1;l<=m;l++){ if(q[l].d!=1) break; a[q[l].x]=a[q[l].y]=1; } for(r=m;r;r--){ if(q[r].c!=2) break; a[q[r].x]=a[q[r].y]=2; qu.push(q[r].x),qu.push(q[r].y); } for(int i=l;i<=r;i++){ ve[q[i].x].push_back(q[i].y); a[q[i].x]=max(a[q[i].x],1); in[q[i].y]++; } for(int i=1;i<=n;i++){ if(!in[i]) qu.push(i); } bfs(); for(int i=1;i<=n;i++){ if(!vis[i]){ qu.push(i); a[i]=1; bfs(); } } int ans=0; for(int i=1;i<=n;i++){ ans+=a[i]; a[i]=vis[i]=in[i]=0; ve[i].clear(); } printf("%d\n",ans); } int main(){ scanf("%d",&T); while(T--) solve(); return 0; }