// Hail god Yato
 
#include <bits/stdc++.h> 
using namespace std;
 
#define hs ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef long long ll;
const ll MOD = 1000000007;
const ll INF = 1e18;
const ll MAX = 200001;
//
//
vector<vector<int>> g(MAX+1);
int parent[MAX+1];
bool circle[MAX+1];
bool vis[MAX+1];
bool dfs(int node){
    vis[node] = 1;
    for(int i : g[node]){
        if(parent[node] == i)
            continue;
        if(vis[i]){
            for(int z = node; z != parent[i]; z = parent[z]){
                // cout<<z<<" ";
                circle[z] = true;
            }
            return true;
        }
        parent[i] = node;
        if(dfs(i))
            return true;
    }
    return false;
}
ll dfs2(int node){
    int size = 0;
    for(int i : g[node]){
        if(i == parent[node] || circle[i])
            continue;
        parent[i] = node;
        size += dfs2(i);
    }
    return size+1;
}
void solve(){
    ll n;
    cin>>n;
    for(int i = 1; i <= n ; i++){
        g[i].clear();
        vis[i] = false;
        circle[i] = false;
        parent[i] = -1;
    }
    for(int i = 1; i <= n; i++){
        int f, s;
        cin>>f>>s;
        g[f].push_back(s);
        g[s].push_back(f);
    }
    bool k = dfs(1);
    ll ans = n*(n-1);
    for(int i = 1; i <= n; i++)
        parent[i] = -1;
    for(int i = 1; i <= n; i++)
        if(circle[i]){
            ll size = dfs2(i);
            ans -= size*(size-1)/2;
        }
    cout<<ans<<"\n";
}
int main(){ 
        hs;
        ll t;
        t=1;
        cin>>t;
        for (int i=1; i<=t; i++){
                //cout<<"Case #"<<i<<": ";
                solve();
         }
        return 0; 
}