#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn = 50005;
int idx[maxn];
int d[maxn];

void init(int n) {
    for(int i = 0; i <= n; i++) {
        idx[i] = i;
        d[i] = 0;
    }
}
int root(int x) {
    if(x == idx[x]) {
        return x;
    }
    int parent = idx[x];
    idx[x] = root(idx[x]);
    d[x] += d[parent];
    return idx[parent];
}

bool unite(int x, int y, int type, int n) {
    if(x >= n or y >= n) {
        return true;
    }
    int root_x = root(x);
    int root_y = root(y);

    int value = ((d[x] - d[y] - type) % 3 + 3) % 3;
    if(root_x == root_y) {
        if(value != 0) {
            return true;
        }
        return false;
    }
    else {
        idx[root_x] = root_y;
        d[root_x] = 3 - value;
        return false;
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    int T;
    cin >> T;

    while(T--) {
        int n, k;
        cin >> n >> k;
        int res = 0;
        init(n);
        for(int i = 0; i < k; i++) {
            int type, x, y;
            cin >> type >> x >> y;
            x--; y--; type--;

            res += unite(x, y, type, n);

        }
        cout << res << "\n";
    }
    return 0;
}