#include <bits/stdc++.h>
#define int long long
#define eb emplace_back
#define pb push_back
#define vi vector<int>
#define vii vector<vi>
#define viii vector<vii>
#define vc vector<char>
#define vcc vector<vc>
#define vb vector<bool>
#define vbb vector<vb>
#define pai pair<int,int>
#define f first
#define s second
using namespace std;
const int M=1e5;
int start,en,n;bool ok;
bool dfs(int u,vi &par,vii &adj,vi &col,int pa){
        col[u]=1;
        for(int it:adj[u]){
            if(it!=pa){
                par[it]=u;
                if(col[it]==1){
                    if(ok)
                        start=it,en=u;ok=false;
                        return true;
                }
                else if(col[it]==0 && dfs(it,par,adj,col,u)){
                    return true;
                }
            }
        }
        col[u]=2;
        return false;
}
void DFS(int u,int pa,vii &adj,vi &sub){
    sub[u]=1;
    for(int it:adj[u]){
        if(it!=pa){
            DFS(it,u,adj,sub);
            sub[u]=sub[u]+sub[it];
        }
    }
}
void solve(){
    cin>>n;ok=true;
    vii adj(n+1);
    for(int i=0;i<n;i++){
        int x,y;cin>>x>>y;
        adj[x].pb(y),adj[y].pb(x);
    }
    vi col(n+1),par(n+1);
    bool check=dfs(1,par,adj,col,0);
    auto it=adj[start].begin();
    while(*it!=en){
        it++;
    }
    adj[start].erase(it);
    it=adj[en].begin();
    while(*it!=start){
        it++;
    }
    adj[en].erase(it);
    vi sub(n+1);
    DFS(1,0,adj,sub);int tot=0,res=n*(n-1),val;
    while(en!=start){
        val=(sub[en]-tot)*(sub[en]-tot-1);val/=2;
        res=res-val;tot+=(sub[en]-tot);
        en=par[en];
    }
    val=n-tot;
    res=res-((val)*(val-1))/2;
    cout<<res<<'\n';
}
int32_t main(){
    #ifndef ONLINE_JUDGE
    // for getting input from input.txt
    freopen("input.txt", "r", stdin);
    // for writing output to output.txt
    freopen("out.txt", "w", stdout);
    #endif
    int t;cin>>t;
    while(t--){
        solve();
    }
}