Code: Minimum Path Cover

/**
 *    author:  tourist
 *    created: 28.03.2026 08:06:35
 **/
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt;
    cin >> tt;
    while (tt--) {
        int n;
        cin >> n;
        vector<int> ans(n);
        vector<vector<int64_t>> f(n);
        vector<int64_t> new_f;
        for (int i = n - 1; i >= 0; i--) {
            int64_t v;
            cin >> v;
            int k;
            cin >> k;
            auto Add = [&](int64_t x) {
                new_f.clear();
                for (auto y : f[i]) {
                    auto g = gcd(x, y);
                    if (g > 1) {
                        new_f.push_back(g);
                    }
                    if (g < y) {
                        new_f.push_back(y / g);
                    }
                    x /= g;
                }
                if (x > 1) {
                    new_f.push_back(x);
                }
                swap(f[i], new_f);
            };
            for (int j = 0; j < k; j++) {
                int u;
                cin >> u;
                --u;
                ans[i] += ans[u];
                for (auto g : f[u]) {
                    g = gcd(g, v);
                    if (g > 1) {
                        Add(g);
                    }
                }
            }
            if (f[i].empty()) {
                ans[i] += 1;
                f[i].push_back(v);
            }
            cout << ans[i] << endl;
        }
    }
    return 0;
}