#include<bits/stdc++.h> #define int long long using namespace std; void init(){ freopen("max.in","r",stdin); freopen("max.out","w",stdout); } int n,m; vector<pair<int,int> >opt[10]; pair<int,int> num[100010]; pair<int,pair<int,int> >que[100010]; signed main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cin>>t; while(t--){ memset(num,0,sizeof(num)); opt[1].clear(); opt[2].clear(); opt[3].clear(); opt[4].clear(); int siz=0; cin>>n>>m; for(int i=1;i<=m;i++){ int x1,a1,x2,a2; cin>>x1>>a1>>x2>>a2; if(a1==1&&a2==1)opt[1].push_back(make_pair(x1,x2)); else if(a1==1&&a2==2)opt[2].push_back(make_pair(x1,x2)); else if(a1==2&&a2==1)opt[3].push_back(make_pair(x1,x2)); else opt[4].push_back(make_pair(x1,x2)); } int t=0; for(int i=0;i<opt[1].size();i++){ t++; num[opt[1][i].first].first=num[opt[1][i].second].first=1; num[opt[1][i].first].second=num[opt[1][i].second].second=t; } for(int i=0;i<opt[2].size();i++){ if(num[opt[2][i].first].first==2){ if(num[opt[2][i].second].first==0){ t++; num[opt[2][i].second]=make_pair(2,t); }else if(num[opt[2][i].second].first==1){ siz++; que[siz]=make_pair(2,opt[2][i]); }else{ continue; } }else{ t++; num[opt[2][i].first]=make_pair(1,t),num[opt[2][i].second]=make_pair(2,t); } } for(int i=0;i<opt[3].size();i++){ if(num[opt[3][i].second].first==2){ if(num[opt[3][i].first].first==0){ t++; num[opt[3][i].first]=make_pair(2,t); }else if(num[opt[3][i].first].first==1){ siz++; que[siz]=make_pair(3,opt[3][i]); }else{ continue; } }else{ t++; num[opt[3][i].first]=make_pair(2,t),num[opt[3][i].second]=make_pair(1,t); } } for(int i=0;i<opt[4].size();i++){ t++; num[opt[4][i].first]=make_pair(2,t),num[opt[4][i].second]=make_pair(2,t); } for(int i=1;i<=siz;i++){ pair<int,pair<int,int> >p=que[i]; t++; if(num[p.second.first].first==2&&num[p.second.second].first==2)continue; else if(p.first==2&&num[p.second.first].first==2&&num[p.second.second].first==1&&num[p.second.first].second!=num[p.second.second].second){ num[p.second.second]=make_pair(2,t); }else if(p.first==3&&num[p.second.first].first==1&&num[p.second.second].first==2&&num[p.second.first].second!=num[p.second.second].second){ num[p.second.first]=make_pair(2,t); } } int ans=0; for(int i=1;i<=n;i++)ans+=num[i].first; cout<<ans<<endl; } return 0; }