#include <bits/stdc++.h>
using namespace std;
void addEdge(vector<long long int> al[],long long int u,long long int v){
    al[u].push_back(v);
    al[v].push_back(u);
}
 
void chainHandler(long long int u,long long int v,vector <long long int> &chain,vector <long long int>al[],
long long int visited[],bool &m1){
   visited[u]=1;
   chain.push_back(u);
   long long int i;
   for(i=0;i<(al[u].size()) && m1==false;i++){
       if(visited[al[u][i]]==1 && al[u][i]!=v){
           m1=true;
           long long int j;
           for(j=0;j<chain.size();j++){
               if(chain[j]==al[u][i])
                    break;
           }
           vector <long long int> :: iterator i1=chain.begin(),i2=chain.begin()+j;
           chain.erase(i1,i2);
       }
       else if(visited[al[u][i]]==0){
           chainHandler(al[u][i],u,chain,al,visited,m1);
       }
   }
   if(m1==false)
        chain.pop_back();
}
void branchCount(long long int u,vector <long long int>al[],long long int cp[],long long int visited[],long long int &count){
    count++;
    visited[u]=1;
    long long int i;
    for(i=0;i<(al[u].size());i++){
        if(visited[al[u][i]]==0 && cp[al[u][i]]==0)
            branchCount(al[u][i],al,cp,visited,count);
    }
}
int main(){
    long long int t;
    cin >> t;
    while(t--){
        long long int n;
        cin >> n;
        long long int i,u,v,visited[n+1];
        vector <long long int> al[n+1],chain;
        for(i=0;i<=n;i++)
            visited[i]=0;
        for(i=0;i<n;i++){
            cin >> u >> v;
            addEdge(al,u,v);
        }
        /*for(i=1;i<=n;i++){
            for(int j=0;j<al[i].size();j++)
                cout << al[i][j] << " ";
            cout <<endl;
        }*/
      //  cout << "******\n";
        bool m1=false;
        chainHandler(1,1,chain,al,visited,m1);
        /*for(i=0;i<chain.size();i++)
            cout << chain[i] << " ";
        cout << endl;*/
        long long int cp[n+1];
        for(i=0;i<=n;i++)
            cp[i]=0;
        for(i=0;i<chain.size();i++)
            cp[chain[i]]=1;
        for(i=0;i<=n;i++)
            visited[i]=0;
        long long int sum=0;
        long long int count=0;
        for(i=0;i<(chain.size());i++){
            count=0;
            branchCount(chain[i],al,cp,visited,count);
           // cout << count << " " << chain[i] << endl;
            sum+=((count)*(count-1))/2;
        }
        long long int ans=(n-1)*n-sum;
        cout << ans<<endl;
        
        
    }
    return 0;
}