#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
typedef long long ll;
typedef pair<ll,ll>pll;
typedef long double ld;
ll bin_pow(ll a,ll b){
    if(b==0)return 1;
    if(b%2==0){
        ll t=bin_pow(a,b/2);
        return t*t%MOD;
    }
    else return a*bin_pow(a,b-1)%MOD;
}
vector<ll>graph[200000];
ll p[200000],sz[200000];
bool used[200000];
ll pred(ll x){
    if(x==p[x])return x;
    return p[x]=pred(p[x]);
}
bool same(ll x,ll y){return pred(x)==pred(y);}
void unite(ll x,ll y){
    x=pred(x);
    y=pred(y);
    if(sz[x]>sz[y])swap(x,y);
    sz[y]+=sz[x];
    p[x]=y;
}
ll comp;
void dfs(ll x){
    used[x]=1;
    comp++;
    for(auto u : graph[x]){
        if(used[u])continue;
        dfs(u);
    }
}
int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll t=1,n,m,k=0,sum=0,l=0,r=0,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
    cin>>t;
    while(t--){
            ans=z=0;
        cin>>n;
        for(int i=0;i<n;i++)graph[i].clear(),p[i]=i,sz[i]=1;
        vector<pll>edges;
        for(int i=0;i<n;i++){
            cin>>x>>y;
            x--,y--;
            edges.push_back({x,y});
        }
        for(int i=0;i<n;i++)used[i]=0;
        for(int i=0;i<n;i++){
            x=edges[i].first,y=edges[i].second;
            if(same(x,y)){
                l=x;
                r=y;
                break;
            }
            unite(x,y);
        }
         for(int i=0;i<n;i++){
            x=edges[i].first,y=edges[i].second;
            if(x==l&&y==r)continue;
            graph[x].push_back(y);
            graph[y].push_back(x);
        }
        queue<ll>q;
        q.push(l);
        for(int i=0;i<n;i++)p[i]=-1;
        while(!q.empty()){
            x=q.front();
            used[x]=1;
            q.pop();
            for(auto u : graph[x]){
                if(used[u])continue;
                q.push(u);
                p[u]=x;
            }
        }
        vector<ll>b,c;
        y=0;
        for(int i=0;i<n;i++)used[i]=0;
        while(r!=-1){
            used[r]=1;
            c.push_back(r);
            y++;
            r=p[r];
        }
        for(int i=0;i<y;i++){
            used[c[i]]=0;
            comp=0;
            dfs(c[i]);
            b.push_back(comp);
        }
        //while(b.size()<y)b.push_back(1);
        ans=n*(n-1)/2;
        x=0;

        for(auto u : b){
                //cout<<u<<endl;
            x+=u*(n-u);
        }
        ans+=x/2;
        cout<<ans;
        cout<<"\n";
    }
    return 0;
}
