Untitled

#include<bits/stdc++.h>
#define ll long long
#define LL long long
#define MOD1 (987777733LL)
#define MOD2 (1010101333LL)
#define endl '\n'
#define SZ(x) ((int)x.size())
#define MXN (1000005)
#define INF (1e9)
#define rep(i,l,r) for(int i=l;i<r;i++)
using namespace std;

mt19937 gen(880907);

template<typename T1,typename T2>
ostream& operator<<(ostream& out,const pair<T1,T2>& p){
	out<<p.first<<" "<<p.second;
	return out;
}

// #define DEBUG

template<typename T1,typename T2>
pair<ll,ll> operator*(pair<T1,T1> lhs,pair<T2,T2> rhs){
    pair<ll,ll> ret;
    ret.first = lhs.first*rhs.first%MOD1;
    ret.second = lhs.second*rhs.second%MOD2;
    return ret;
}
template<typename T1,typename T2>
pair<ll,ll> operator+(pair<T1,T1> lhs,pair<T2,T2> rhs){
    pair<ll,ll> ret;
    ret.first = (lhs.first+rhs.first)%MOD1;
    ret.second = (lhs.second+rhs.second)%MOD2;
    return ret;
}

//rotate(begin(s),begin(s)+minRotation(s),end(s))
int minRotation(vector<ll> s) {
    int a = 0, N = s.size();
    for(int i=0;i<N;i++)    s.push_back(s[i]);
    rep(b,0,N) rep(k,0,N) {
        if(a+k == b || s[a+k] < s[b+k]){
            b += max(0, k-1); break;
        }
        if(s[a+k] > s[b+k]) {
            a = b; break;
        }
    } 
    return a;
}

int n,o;
int sz[MXN];
bool flag,finish;
bool v[MXN],c[MXN];
bool isprime[20000007];
vector<ll> val,primes;
vector<int> cycle;
vector<vector<int>> edge;
set<vector<ll>> ans;

void dfs(int x,int f){
    if(finish)  return;
    if(v[x]){
        flag=1;
        o=x;
        return;
    }
    v[x]=1;
    for(auto i:edge[x]){
        if(i==f)    continue;
        dfs(i,x);
        if(flag)    break;
    }
    if(finish)  return;
    if(flag){
        cycle.push_back(x);
        c[x]=1;
        if(x==o)    finish=1;
    }
}

pair<ll,ll> Hash(int x,int f){
    pair<ll,ll> ret=make_pair(0,0);
    vector<pair<ll,ll>> h;
    sz[x]=1;
    for(auto i:edge[x]){
        if(i==f||c[i])    continue;
        h.push_back(Hash(i,x));
        sz[x]+=sz[i];
    }
    sort(h.begin(),h.end());
    for(auto i:h){
        ret=ret*make_pair(primes[sz[x]],primes[sz[x]])+i;
    }
    ret = ret*make_pair(primes[sz[x]],primes[sz[x]])+make_pair(1,1);
    val[x] = ret.first*ret.second;
    return ret;
}

void build(){
    for(ll i=2;i<=20000000;i++){
        if(isprime[i])  continue;
        primes.push_back(i);
        for(ll j=i*i;j<=20000000;j+=i){
            isprime[j]=1;
        }
    }
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    build();
    shuffle(primes.begin(),primes.end(),gen);
    int t; cin>>t;
    while(t--){
        cin>>n;
        ans.clear();
        for(int i=0,m;i<n;i++){
            cin>>m;
            val.clear();val.resize(m);
            edge.clear();edge.resize(m);
            for(int j=0,a,b;j<m;j++){
                cin>>a>>b;
                edge[a-1].push_back(b-1);
                edge[b-1].push_back(a-1);
            }
            flag=finish=0;
            for(int j=0;j<m;j++)    c[j]=v[j]=0;
            cycle.clear();
            o=-1;
            dfs(0,0);
            vector<ll> tmp1,tmp2;
            for(auto j:cycle){
                Hash(j,j);
                tmp1.push_back(val[j]);
            }
            rotate(tmp1.begin(),tmp1.begin()+minRotation(tmp1),tmp1.end());
            tmp2=tmp1;
            reverse(tmp2.begin(),tmp2.end());
            rotate(tmp2.begin(),tmp2.begin()+minRotation(tmp2),tmp2.end());
            ans.insert(min(tmp1,tmp2));
        }
        cout<<ans.size()<<endl;
    }
    return 0;
}