#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 10; struct node { int x,a,y,b; bool operator < (node nd) const { return a + b < nd.a + nd.b; } } opt[N]; int T,ans,n,m,a[N],stk[N],top,low[N],dfn[N],cnt,book[N],mark[N],leg[N],tot,bel[N],out[N],tag[N]; vector <int> G[N],E[N],scc[N]; void Tarjan(int x) { dfn[x] = low[x] = ++cnt; stk[++top] = x; book[x] = 1; for(int y : G[x]) { if(!dfn[y]) Tarjan(y),low[x] = min(low[x],low[y]); else if(book[y]) low[x] = min(low[x],dfn[y]); } if(low[x] == dfn[x]) { ++tot; while(1) { int now = stk[top]; top--; leg[tot] |= mark[now]; bel[now] = tot; book[now] = 0; scc[tot].push_back(now); if(now == x) break; } } } void solve() { cin >> n >> m; ans = 0; cnt = 0; tot = 0; top = 0; for(int i = 1;i <= m;i++) cin >> opt[i].x >> opt[i].a >> opt[i].y >> opt[i].b; sort(opt + 1,opt + m + 1); for(int i = 1;i <= m;i++) { tag[opt[i].x] = 1,tag[opt[i].y] = 1; if(opt[i].a + opt[i].b == 3) { if(opt[i].a == 2) swap(opt[i].a,opt[i].b),swap(opt[i].x,opt[i].y); G[opt[i].y].push_back(opt[i].x); } else if(opt[i].a == 2 && opt[i].b == 2) mark[opt[i].x] = 1,mark[opt[i].y] = 1; } for(int i = 1;i <= n;i++) if(!dfn[i]) Tarjan(i); for(int i = 1;i <= n;i++) { for(int x : G[i]) { if(bel[x] == bel[i]) continue; E[bel[i]].push_back(bel[x]); out[bel[i]]++; } } for(int i = 1;i <= n;i++) if(!tag[i]) ans--; for(int i = 1;i <= tot;i++) { if(!out[i] && !leg[i]) ans--; for(int x : scc[i]) a[x] = 2; } for(int i = 1;i <= n;i++) ans += a[i]; cout << ans << "\n"; for(int i = 1;i <= tot;i++) E[i].clear(); for(int i = 1;i <= n;i++) tag[i] = 0,G[i].clear(),mark[i] = 0,a[i] = 0,dfn[i] = 0,low[i] = 0,book[i] = 0; for(int i = 1;i <= tot;i++) leg[i] = 0,E[i].clear(),out[i] = 0,bel[i] = 0; } int main() { //freopen("max4.in.txt","r",stdin); //freopen("max.out.txt","w",stdout); ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> T; while(T--) solve(); return 0; }