#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int T;cin>>T;while(T--){int n;cin>>n;vector<vector<int>>g(n);vector<int>deg(n),size(n,1);for(int i=0,u,v;i<n;++i){cin>>u>>v;--u;--v;g[u].push_back(v);g[v].push_back(u);++deg[u];++deg[v];}queue<int>q;for(int i=0;i<n;++i)if(deg[i]==1)q.push(i);while(!q.empty()){int u=q.front();q.pop();deg[u]=0;for(int v:g[u])if(deg[v]>0){size[v]+=size[u];if(--deg[v]==1)q.push(v);}}long long ans=1LL*n*(n-1);for(int i=0;i<n;++i)if(deg[i]>0)ans-=1LL*size[i]*(size[i]-1)/2;cout<<ans<<'\n';}}