// Author: Aquizahv #include <bits/stdc++.h> using namespace std; const int N = 1e5 + 5; int n, m, a[N], pos; pair<int, int> e[N]; vector<int> g[N]; bool mark[N]; int dfncnt, dfn[N], low[N], scccnt, id[N]; int stk[N], tp; bool instk[N]; vector<int> scc[N]; void tarjan(int u) { // cerr << u << endl; dfn[u] = low[u] = ++dfncnt; stk[++tp] = u; instk[u] = true; for (auto v : g[u]) { if (!dfn[v]) { tarjan(v); low[u] = min(low[u], low[v]); } else if (instk[v]) low[u] = min(low[u], dfn[v]); } if (dfn[u] == low[u]) { int v; scccnt++; do { v = stk[tp--]; instk[v] = false; id[v] = scccnt; scc[scccnt].push_back(v); } while (v != u); } } void init() { dfncnt = scccnt = pos = 0; for (int i = 1; i <= n; i++) { mark[i] = 0; a[i] = id[i] = dfn[i] = low[i] = 0; g[i].clear(); scc[i].clear(); } } inline int read() { int x = 0; char ch = getchar(); while (ch < '0' || ch > '9') { ch = getchar(); } while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); } return x; } void solve() { n = read(); m = read(); init(); int u, x, v, y; for (int i = 1; i <= m; i++) { u = read(); x = read(); v = read(); y = read(); if (x == 1 && y == 1) a[u] = max(a[u], 1), a[v] = max(a[v], 1); else { a[u] = a[v] = 2; if (x == 2 && y == 2) mark[u] = mark[v] = true; else if (x == 2 && y == 1) { e[++pos] = {u, v}; g[u].push_back(v); } else if (x == 1 && y == 2) { e[++pos] = {v, u}; g[v].push_back(u); } } } for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i); for (int i = 1; i <= n; i++) g[i].clear(); for (int i = 1; i <= pos; i++) if (id[e[i].first] != id[e[i].second]) g[id[e[i].first]].push_back(id[e[i].second]); int ans = 0; for (int i = 1; i <= scccnt; i++) if (!g[i].size() && a[scc[i][0]] == 2) { bool flag = false; for (int v : scc[i]) flag |= mark[v]; ans -= !flag; } for (int i = 1; i <= n; i++) { // cout << a[i] << " \n"[i == n]; ans += a[i]; } printf("%d\n", ans); } int main() { int T; T = read(); while (T--) solve(); return 0; }