#include <bits/stdc++.h>
using namespace std;
#define all(v) (v).begin(),(v).end()
#define pb(a) push_back(a)
#define rep(i, n) for(int i=0;i<n;i++)
#define foa(e, v) for(auto&& e : v)
using ll = long long;
const ll MOD7 = 1000000007, MOD998 = 998244353, INF = (1LL << 60);
#define dout(a) cout<<fixed<<setprecision(10)<<a<<endl;

struct RollingHash {
    static const int base1 = 1007, base2 = 2009;
    static const int mod1 = 1000000007, mod2 = 1000000009;
    std::vector<long long> hash1, hash2, power1, power2;
 
    // construct
    RollingHash(const vector<int> &S) {
        int n = (int)S.size();
        hash1.assign(n+1, 0);
        hash2.assign(n+1, 0);
        power1.assign(n+1, 1);
        power2.assign(n+1, 1);
        for (int i = 0; i < n; ++i) {
            hash1[i+1] = (hash1[i] * base1 + S[i]) % mod1;
            hash2[i+1] = (hash2[i] * base2 + S[i]) % mod2;
            power1[i+1] = (power1[i] * base1) % mod1;
            power2[i+1] = (power2[i] * base2) % mod2;
        }
    }
    
    // get hash of S[left:right)
    inline std::pair<long long, long long> get(int l, int r) const {
        long long res1 = hash1[r] - hash1[l] * power1[r-l] % mod1;
        if (res1 < 0) res1 += mod1;
        long long res2 = hash2[r] - hash2[l] * power2[r-l] % mod2;
        if (res2 < 0) res2 += mod2;
        return {res1, res2};
    }
};


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int t; cin >> t;
    map<vector<int>, int> mp;
    int rt_id = 0;
    
    rep(_, t) {
        unordered_set<ll> st;
        int cnt = 0;
        int m; cin >> m;
        rep(k, m) {
            int n; cin >> n;
            vector<vector<int>> v(n);
            rep(i, n) {
                int a, b;
                cin >> a >> b;
                a --; b --;
                v[a].pb(b);
                v[b].pb(a);
            }
            vector<int> heiro;
            vector<bool> seen(n, 0);
            int sta = -1;
            auto dfs = [&](auto dfs, int now, int p) -> bool {
                if(seen[now]) {
                    heiro.pb(now);
                    sta = now;
                    return true;
                }
                seen[now] = 1;
                foa(e, v[now]) {
                    if(e == p) continue;
                    bool ret = dfs(dfs, e, now);
                    if(ret) {
                        if(sta == now) {
                            return false;
                        }
                        heiro.pb(now);
                        return true;
                    } 
                }
                return false;
            };
            dfs(dfs, 0, -1);
            int sz = heiro.size();
            auto dfs1 = [&](auto dfs1, int now, int p) -> int {
                vector<int> vec;
                foa(e, v[now]) {
                    if(e == p) continue;
                    vec.pb(dfs1(dfs1, e, now));
                }
                sort(all(vec));
                if(mp.count(vec)) {
                    return mp[vec];
                }
                mp[vec] = rt_id ++;
                return mp[vec];
            };

            vector<int> nodes;
            rep(i, sz) {
                int v1 = heiro[(i + sz - 1) % sz];
                int v2 = heiro[(i + 1) % sz];
                vector<int> vec;
                foa(e, v[heiro[i]]) {
                    if(v1 == e or v2 == e) continue;
                    vec.pb(dfs1(dfs1, e, heiro[i]));
                }
                sort(all(vec));
                if(mp.count(vec)) {
                    nodes.pb(mp[vec]);
                } else {
                    mp[vec] = rt_id ++;
                    nodes.pb(mp[vec]);
                }
            }
            rep(i, sz) nodes.pb(nodes[i]);
            RollingHash r(nodes);
            bool flag = 0;
            rep(i, sz) {
                auto [r1, r2] = r.get(i, i + sz);
                if(st.count((r1 << 30) | r2)) {
                    flag = 1;
                    break;
                }
            }
            if(flag) continue;
            reverse(all(nodes));
            RollingHash re(nodes);
            rep(i, sz) {
                auto [r1, r2] = re.get(i, i + sz);
                if(st.count((r1 << 30) | r2)) {
                    flag = 1;
                    break;
                }
            }
            if(flag) continue;
            auto [r1, r2] = re.get(0, sz);
            st.insert((r1 << 30) | r2);
            cnt ++;
        }
        cout << cnt << '\n';
    }
    return 0;
}