#include <bits/stdc++.h>
using namespace std;

// #define ls n << 1
// #define rs n << 1 | 1
 #define PB push_back
 #define MP make_pair
 #define int long long
// #define us unsigned
// #define LL long long
 const int N = 5e5;
// const int M = 2e;
// #define re register
// const int mod = 10000;
// const double eps = 1e-8;
// inline char nc()
// {
//     static char buf[1000000], *p1 = buf, *p2 = buf;
//     return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++;
// }
// #define getchar nc
inline int read()
{
    int s = 0;
    register bool neg = 0;
    register char c = getchar();
    for (; c < '0' || c > '9'; c = getchar())
        neg |= (c == '-');
    for (; c >= '0' && c <= '9'; s = s * 10 + (c ^ 48), c = getchar())
        ;
    s = (neg ? -s : s);
    return s;
}

int t,a,vis[N+10],siz[N+10];
bool p[N+10];
vector<int> st[N+10];

inline void dfs(int n) {
	for(int i=0;i<st[n].size();i++) {
		int v=st[n][i];
//		cout<<v<<endl;
		if(vis[v]!=1) {
			vis[v]--;
			if(vis[v]==1)
				dfs(v);
		}
	}
}

inline void Dfs(int n,int fa) {
	siz[n]=1;
	for(int i=0;i<st[n].size();i++) {
		int v=st[n][i];
		if(v==fa) continue;
        if(vis[v]==1) {
			Dfs(v,n);
			siz[n]+=siz[v];
		}
	}
}

signed main()
{
//	freopen("in.txt","r",stdin);
	t=read();
	while(t--) {
		a=read();
		for(int i=1;i<=a;i++) siz[i]=vis[i]=p[i]=0,st[i].clear();
		int x,y;
		for(int i=1;i<=a;i++) {
			x=read();
			y=read();
			st[x].PB(y);
			st[y].PB(x);
			vis[x]++;
			vis[y]++;
			if(vis[x]!=1) p[x]=1;
			if(vis[y]!=1) p[y]=1;
		}
//		for(int i=1;i<=a;i++) cout<<vis[i]<<' ';
//		cout<<endl;
		for(int i=1;i<=a;i++) if(!p[i]) dfs(i);
//		for(int i=1;i<=a;i++) cout<<vis[i]<<' ';
//		cout<<endl;
		int tmp=0,ans=0;
		for(int i=1;i<=a;i++) if(vis[i]==2) {
			Dfs(i,0);
			ans+=tmp*siz[i]*2;
			ans+=siz[i]*(siz[i]-1)/2;
			tmp+=siz[i];
//			cout<<siz[i]<<endl;
		}
		printf("%lld\n",ans);
		
	}
    return 0;
}