#include<bits/stdc++.h> using namespace std; const int N=1e5+10; #define pb push_back int T,n,m,rd[N],rdd[N],ans; bool book[N],v[N],t[N],vis[N]; struct opr{int x,c,y,d;}p[N]; vector<int>e[N]; queue<int>q; void topo(){ for(int i=1;i<=n;i++){if((rd[i]==0&&t[i])||book[i]){q.push(i);vis[i]=1;/*cout<<i<<" "<<rd[i]<<" "<<book[i]<<endl;*/}}//cout<<endl; while(!q.empty()){ int u=q.front();q.pop(); // cout<<u<<" "; if(rd[u]==0&&(!book[u])){ans++;} else {ans+=2;} for(auto v:e[u]){rdd[v]--;if(!vis[v]){q.push(v);vis[v]=1;}} } } void dfs(int u){ vis[u]=1;ans+=2; for(auto v:e[u]){ if(vis[v])continue; dfs(v); } } inline void init(){ for(int i=1;i<=N-5;i++){v[i]=book[i]=t[i]=vis[i]=0;rd[i]=0;e[i].clear();} ans=0; } map<pair<int,int>,bool>mp; signed main(){ scanf("%d",&T); while(T--){ init(); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ scanf("%d%d%d%d",&p[i].x,&p[i].c,&p[i].y,&p[i].d); if(p[i].c==1&&p[i].d==1){t[p[i].x]=t[p[i].y]=v[p[i].x]=v[p[i].y]=1;} if(p[i].c==2&&p[i].d==2){t[p[i].x]=t[p[i].y]=book[p[i].x]=book[p[i].y]=1;} if(p[i].c==1&&p[i].d==2){ if(!mp[{p[i].x,p[i].y}]){e[p[i].x].pb(p[i].y);rd[p[i].y]++;} t[p[i].x]=t[p[i].y]=1; } if(p[i].c==2&&p[i].d==1){ if(!mp[{p[i].x,p[i].y}]){e[p[i].y].pb(p[i].x);rd[p[i].x]++;} t[p[i].x]=t[p[i].y]=1; } } for(int i=1;i<=n;i++)rdd[i]=rd[i]; topo(); for(int i=1;i<=n;i++){ if((!vis[i])&&t[i]){dfs(i);ans--;} } printf("%d\n",ans); } return 0; }