D_Connect_the_Dots.cpp

#include <bits/stdc++.h>
using namespace std;
// First you make it work, then you can always make it beautiful

const int inf = 1e9;
class DSU {
public:
    vector<int> par, sz;
    DSU(int n){
        par.resize(n + 1);
        iota(par.begin(), par.end(), 0);
        sz.resize(n + 1, 1);
    }
    int find(int x){
        return x == par[x] ? x : par[x] = find(par[x]);
    }
    bool merge(int u, int v) {
        int p1 = find(u), p2 = find(v);
        if (p1 == p2) return 0;
        if (sz[p1] < sz[p2]) swap(p1, p2);
        par[p2] = p1;
        sz[p1] += sz[p2];
        return 1;
    }
};
void solve() {
    int n, m;
    cin >> n >> m;

    DSU ds(n);
    vector<vector<int>> pre(11,vector<int>(n + 1));
    vector<vector<int>> end(11,vector<int>(n + 1));

    for(int i=0;i<m;i++) {
        int a, d, k;
        cin >> a >> d >> k;
        pre[d][a]++;
        if(a + (k+1)*d <= n)
        end[d][a + (k+1)*d]++;
    }

    for(int d=1;d<=10;d++) {
        for(int start = 1; start <= d; start++) {
            int curr = 0;
            int prev = -1;
            for(int i=start;i<=n;i+=d) {
                curr -= end[d][i];
                bool isprev = (curr > 0);
                curr += pre[d][i];
                if(curr > 0) {
                    if(isprev) {
                        ds.merge(prev, i);
                    }
                    prev = i;
                }
            }
        }
    }

    int ans = 0;
    for(int i=1;i<=n;i++) {
        if(ds.find(i) == i) ans++;
    }
    cout << ans << "\n";

}


int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int _;
    cin >> _;
    while (_-->0) {
        solve();
    }

    return 0;
}