#include<bits/stdc++.h> using namespace std; const int N = 1e5+10; int T,n,m,f[N],stk[N],low[N],cnt,tot,k,instk[N],dfn[N],siz[N],col[N],col2[N],fa[N],ind[N],vis[N]; vector<int> G[N]; vector<int> G2[N]; vector<int> G3[N]; struct Q{ int x; int c; int y; int d; }a[N]; void Tarjan(int x){ dfn[x]=low[x]=++cnt; instk[x]=1; stk[++k]=x; for(int i=0;i<G[x].size();i++){ int v=G[x][i]; if(!dfn[v]){ Tarjan(v); low[x]=min(low[x],low[v]); } else if(instk[v]){ low[x]=min(low[x],dfn[v]); } } if(dfn[x]==low[x]){ ++tot; while(k){ int y=stk[k--]; instk[y]=0; f[y]=tot; siz[tot]++; G3[tot].push_back(y); if(y==x) break; } } } int find(int x){ if(fa[x]==x) return x; else return fa[x]=find(fa[x]); } void merge(int x,int y){ int fx=find(x),fy=find(y); if(fx!=fy){ fa[fx]=fy; } } int main(){ cin>>T; while(T--){ cin>>n>>m; memset(vis,0,sizeof(vis)); memset(col,0,sizeof(col)); memset(col2,0,sizeof(col2)); memset(f,0,sizeof(f)); memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); memset(instk,0,sizeof(instk)); memset(stk,0,sizeof(stk)); memset(siz,0,sizeof(siz)); for(int i=1;i<=n;i++){ fa[i]=i; } memset(ind,0,sizeof(ind)); for(int i=1;i<=n;i++) G[i].clear(); for(int i=1;i<=n;i++) G2[i].clear(); for(int i=1;i<=n;i++) G3[i].clear(); cnt=0; tot=0; k=0; for(int i=1;i<=m;i++){ cin>>a[i].x>>a[i].c>>a[i].y>>a[i].d; vis[a[i].x]=1; vis[a[i].y]=1; if(a[i].c==1&&a[i].d==1){ col[a[i].x]=a[i].c; col[a[i].y]=a[i].d; } if(a[i].c==2&&a[i].d==2){ col2[a[i].x]=a[i].c; col2[a[i].y]=a[i].d; } if(a[i].c==1&&a[i].d==2){ G[a[i].y].push_back(a[i].x); } if(a[i].c==2&&a[i].d==1){ G[a[i].x].push_back(a[i].y); } } for(int i=1;i<=n;i++){ if(!dfn[i]){ Tarjan(i); } } for(int i=1;i<=m;i++){ if(a[i].c==1&&a[i].d==2){ if(f[a[i].x]!=f[a[i].y]){ G2[f[a[i].y]].push_back(f[a[i].x]); ind[f[a[i].y]]++; } } if(a[i].c==2&&a[i].d==1){ if(f[a[i].x]!=f[a[i].y]){ G2[f[a[i].x]].push_back(f[a[i].y]); ind[f[a[i].x]]++; } } } for(int i=1;i<=tot;i++){ if(ind[i]==0){ if(siz[i]==1&&vis[G3[i][0]]==0){ continue; } if(siz[i]==1){ col[G3[i][0]]=1; } else{ int bz=0; for(int j=0;j<G3[i].size();j++){ int v=G3[i][j]; if(col2[v]==2&&bz==0){ col[v]=1; bz=v; } else{ col[v]=2; } } if(bz==0){ col[G3[i][0]]=1; } } } else{ for(int j=0;j<G3[i].size();j++){ int v=G3[i][j]; col[v]=2; } } } for(int i=1;i<=n;i++){ if(col2[i]==2){ col[i]=2; } } int ans=0; for(int i=1;i<=n;i++){ ans=ans+col[i]; } cout<<ans<<endl; } return 0; }