RT

我直接一脸问号……真就只过了样例呗？？？

#include<bits/stdc++.h>
using namespace std;
class FastIO{
    private:
        struct control{
            int ct,val;
            control(int Ct,int Val=-1):ct(Ct),val(Val){}
            inline control operator()(int Val){
                return control(ct,Val);
            }
        }_endl,_prs,_setprecision;
        #define IOSIZE 10000000
        char in[IOSIZE],*p,*pp,out[IOSIZE],*q,*qq,ch[20],*t,b,K,prs;
        inline char getch(){
            return p==pp&&(pp=(p=in)+fread(in,1,IOSIZE,stdin),p==pp)?b=0,EOF:*p++;
        }
        inline void putch(char x){
            q==qq&&(fwrite(out,1,q-out,stdout),q=out),*q++=x;
        }
        inline void puts(const char str[]){fwrite(out,1,q-out,stdout),fwrite(str,1,strlen(str),stdout),q=out;}
        inline void getline(string& s){
            s="";
            for(register char ch;(ch=getch())!='\n'&&b;)s+=ch;
        }
    public:
        FastIO():_endl(0),_prs(1),_setprecision(2),p(in),pp(in),q(out),qq(out+IOSIZE),t(ch),b(1),K(6){}
        ~FastIO(){fwrite(out,1,q-out,stdout);}
        #define endl "\n"
        #define indef(T) inline FastIO& operator>>(T& x){\
            x=0;register char f=0,ch;\
            while(!isdigit(ch=getch())&&b)f|=ch=='-';\
            while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getch();\
            return x=f?-x:x,*this;\
        }
        indef(int)
        indef(long long)
        inline FastIO& operator>>(char& ch){return ch=getch(),*this;}
        inline FastIO& operator>>(string& s){
            s="";register char ch;
            while(isspace(ch=getch())&&b);
            while(!isspace(ch)&&b)s+=ch,ch=getch();
            return *this;
        }
        inline FastIO& operator>>(double& x){
            x=0;register char f=0,ch;
            double d=0.1;
            while(!isdigit(ch=getch())&&b)f|=(ch=='-');
            while(isdigit(ch))x=x*10+(ch^48),ch=getch();
            if(ch=='.')while(isdigit(ch=getch()))x+=d*(ch^48),d*=0.1;
            return x=f?-x:x,*this;
        }
        #define outdef(_T) inline FastIO& operator<<(_T x){\
            !x&&(putch('0'),0),x<0&&(putch('-'),x=-x);\
            while(x)*t++=x%10+48,x/=10;\
            while(t!=ch)*q++=*--t;\
            return *this;\
        }
        outdef(int)
        outdef(long long)
        inline FastIO& operator<<(char ch){return putch(ch),*this;}
        inline FastIO& operator<<(const char str[]){return puts(str),*this;}
        inline FastIO& operator<<(const string& s){return puts(s.c_str()),*this;}
        inline FastIO& operator<<(double x){
            register int k=0;
            this->operator<<(int(x));
            putch('.');
            x-=int(x);
            prs&&(x+=5*pow(10,-K-1));
            while(k<K)putch(int(x*=10)^48),x-=int(x),++k;
            return *this;
        }
        inline FastIO& operator<<(const control& cl){
            switch(cl.ct){
                case 0:putch('\n');break;
                case 1:prs=cl.val;break;
                case 2:K=cl.val;break;
            }
            return *this;
        }
        inline operator bool(){return b;}
}io;
#define int long long
int t,n,d[200005],tot,siz[200005],x,y,ans,h[200005];
queue<int>q;
struct Edge{
	int v,nxt;
	Edge(int _v=0,int _nxt=0){v=_v,nxt=_nxt;}
}e[400005];
inline void add(int u,int v){
	d[u]++,d[v]++;
	e[++tot]=Edge(v,h[u]),h[u]=tot;
	e[++tot]=Edge(u,h[v]),h[v]=tot;
}
bool v[200005];
void dfs(int x,int f){
	siz[x]=1;
	for(register int i=h[x];i;i=e[i].nxt)if(e[i].v^f)dfs(e[i].v,x),siz[x]+=siz[e[i].v];
}
signed main(){
	#ifndef ONLINE_JUDGE
	freopen("CF1454E.in","r",stdin);
	freopen("CF1454E.out","w",stdout);
	#endif
	io>>t;
	while(t--){
		io>>n;
		memset(siz,0,sizeof(siz));
		memset(h,0,sizeof(h));
		memset(v,0,sizeof(v));
		memset(d,0,sizeof(d));ans=0;
		for(register int i=1;i<=n;i++)io>>x>>y,add(x,y);
		while(q.size())q.pop();
		for(register int i=1;i<=n;i++)if(d[i]==1)q.push(i);
		while(q.size()){
			x=q.front();q.pop();
			for(register int i=h[x];i;i=e[i].nxt)if(--d[e[i].v]==1)q.push(e[i].v);
		}
		for(register int i=1;i<=n;i++)if(d[i]>1)v[i]=1;
		for(register int i=1;i<=n;i++)if(v[i]){
			x=0;
			for(register int j=h[i];j;j=e[j].nxt)if(!v[e[j].v])dfs(e[j].v,i),x+=siz[e[j].v];
			ans+=x*(x+1)>>1;
		}
		io<<n*(n-1)-ans<<endl;
	}
	return 0;
}