#include<bits/stdc++.h> using namespace std; long long _,n,m,sum[100005],bd[100005],rd[100005],xbd[100005],vis[100005]; vector<long long>poi[100005],b2; queue<long long>q; int main(){ scanf("%lld",&_); while(_--){ memset(sum,0,sizeof(sum)); memset(rd,0,sizeof(rd)); memset(bd,0,sizeof(bd)); memset(xbd,0,sizeof(xbd)); memset(vis,0,sizeof(vis)); while(!q.empty())q.pop(); scanf("%lld%lld",&n,&m); for(int i=0;i<=n;i++)poi[i].clear(); for(int i=1;i<=m;i++){ long long a,b,c,d; scanf("%lld%lld%lld%lld",&a,&b,&c,&d); bd[a]=bd[c]=1; if(b==2 && d==2)b2.push_back(a),b2.push_back(c),xbd[a]=xbd[c]=1,q.push(a),q.push(c); else if(b==2)poi[c].push_back(a),rd[a]++; else if(d==2)poi[a].push_back(c),rd[c]++; } for(int i=1;i<=n;i++){ if(rd[i]==0)q.push(i); } while(!q.empty()){ long long now=q.front(); q.pop(); vis[now]=1; for(int i=0;i<poi[now].size();i++){ long long nv=poi[now][i]; xbd[nv]=1; if(vis[nv]==0){ vis[nv]=1; q.push(nv); } } } long long last=1; while(last<=n){ long long flag=0; for(int i=1;i<=n;i++){ if(vis[i]==0){ q.push(i); last=i+1; flag=1; break; } } if(flag==0)break; while(!q.empty()){ long long now=q.front(); q.pop(); vis[now]=1; for(int i=0;i<poi[now].size();i++){ long long nv=poi[now][i]; xbd[nv]=1; if(vis[nv]==0){ vis[nv]=1; q.push(nv); } } } } long long ans=0; for(int i=1;i<=n;i++){ ans+=bd[i]+xbd[i]; } printf("%lld\n",ans); } }