#include<bits/stdc++.h> using namespace std; int n,m; int a[100005]; vector<pair<int,int>>op22; vector<int>e[100005]; bool book[100005]; void read(int &x){ x=0; char c=getchar(); while(!isdigit(c))c=getchar(); while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar(); } bool vis[100005]; int dfn[100005],low[100005],stk[100005],tot,top; bool ins[100005]; int scccnt,scc[100005]; int deg[1000005]; vector<int>vscc[100005]; void tj(int p){ dfn[p]=low[p]=++tot; stk[++top]=p; ins[p]=vis[p]=1; for(int x:e[p]){ if(ins[x])low[p]=min(low[p],low[x]); if(vis[x])continue; tj(x); low[p]=min(low[p],low[x]); } if(low[p]==dfn[p]){ scccnt++; while(top){ vscc[scccnt].push_back(stk[top]); ins[stk[top]]=0; scc[stk[top--]]=scccnt; if(stk[top+1]==p)break; } } } vector<int>E[100005]; void slv(){ read(n),read(m); for(int i=1;i<=m;i++){ int x,y,c,d; read(x),read(c),read(y),read(d); if(c==1&&d==1)a[x]=a[y]=1; else if(c==2&&d==2)book[x]=book[y]=1,op22.push_back({x,y}); else if(c==2&&d==1)e[x].push_back(y); else e[y].push_back(x); } for(int i=1;i<=n;i++){ if(!vis[i])tj(i); } for(int i=1;i<=n;i++){ for(int x:e[i]){ if(scc[i]!=scc[x])E[scc[i]].push_back(scc[x]),deg[scc[x]]++; } } for(int i=1;i<=scccnt;i++){ if(deg[i]==0&&E[i].size()==0&&vscc[i].size()==1)continue; if(E[i].size()==0){ bool found=0; for(int x:vscc[i]){ if(book[x]){ found=1; break; } } for(int x:vscc[i]){ a[x]=2; } if(!found){ a[vscc[i][0]]=1; } } else{ for(int x:vscc[i]){ a[x]=2; } } } for(auto x:op22){ a[x.first]=a[x.second]=2; } int ans=0; for(int i=1;i<=n;i++)ans+=a[i]; cout<<ans<<endl; for(int i=1;i<=n;i++)a[i]=book[i]=vis[i]=dfn[i]=low[i]=ins[i]=scc[i]=0,e[i].clear(); for(int i=1;i<=top;i++)stk[i]=0; for(int i=1;i<=scccnt;i++){ vscc[i].clear(); E[i].clear(); deg[i]=0; } top=tot=scccnt=0; op22.clear(); } int main(){ int T;cin>>T;while(T--) slv(); return 0; }