#include<cmath>
#include<iostream>
#include<sstream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cstdlib>
#include<istream>
#include<vector>
#include<stack>
#include<set>
//#include<unordered_map>
#include<map>
#include<algorithm>
#include<queue>
#define mmp make_pair
#define inf 0x3f3f3f3f
#define llinf 0x7fffffffffffffff
using namespace std;
typedef long long ll;
typedef pair<ll,ll> PP;
typedef double ld;
vector<int>hh[200010];
int ID[200010];
bool orz[200010];
ll siz[200010];
queue<int>q;
void topsort(int n) {
    while(!q.empty()) q.pop();
    for(int i=1;i<=n;++i) {
        if(ID[i]==1) {
            q.push(i);
            orz[i]=true;
        }
    }
    while(!q.empty()) {
        int temp=q.front();
        q.pop();
        orz[temp]=true;
        for(int i=0;i<hh[temp].size();++i) {
            int uu=hh[temp][i];
            if(orz[uu]) continue;
            ID[uu]--;
            ID[temp]--;
            if(ID[uu]==1) {
                q.push(uu);
            }
        }
    }
}
void dfs(int u,int f) {
    siz[u]=1;
    for(int i=0;i<hh[u].size();++i) {
        int v=hh[u][i];
        if(orz[v]==0 || v==f) continue;
        dfs(v,u);
        siz[u]+=siz[v];
    }
}
int main() {
    int T;
    scanf("%d",&T);
    while(T--) {
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;++i) {
            hh[i].clear();
            ID[i]=orz[i]=siz[i]=0;
        }
        for(int i=1;i<=n;++i) {
            int x,y; scanf("%d %d",&x,&y);
            hh[x].push_back(y); hh[y].push_back(x);
            ++ID[x]; ++ID[y];
        }
        topsort(n);
        ll cnt=0;
        for(int i=1;i<=n;++i) {
            if(orz[i]==0) {
                ++cnt;
                dfs(i,0);
            }
        }
        ll sum=0;
        ll ans=cnt*(cnt-1);
        for(int i=1;i<=n;++i) {
            if(!orz[i]) {
                ans+=1ll*(cnt-1)*2*(siz[i]-1);
                ans+=1ll*(siz[i]-1)*siz[i]/2;
                sum+=siz[i]-1;
            }
        }
        for(int i=1;i<=n;++i) {
            if(!orz[i]) {
                ans+=1ll*(sum-siz[i]+1)*(siz[i]-1);
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}
