#include<iostream>

#include<queue>
#include<stack>
#include<vector>
#include<algorithm>
#include<stack>
#define double long double
#include<map>

#define MOD 998244353
#define int long long

using namespace std;
vector<char> color;
vector<int> parent;
int cycle_start, cycle_end;

int dfs(int v,bool* visited,vector<vector<int>>& adj)
{
    visited[v]=true;
    int total=0;
    for(int x:adj[v])
    {
       if(!visited[x])
       {
           visited[x]=true;
           total+=1+dfs(x,visited,adj);
       }
    }
    return total;
    
}
int permute(int n,int i)
{
    int mul=1;
    for(int j=n-i+1;j<=n;j++)
    {
        mul*=j;
    }
    return mul/2;
}
bool dfs2(int v, int par,vector<vector<int>>& adj) { // passing vertex and its parent vertex
    color[v] = 1;
    for (int u : adj[v]) {
        if(u == par) continue; // skipping edge to parent vertex
        if (color[u] == 0) {
            parent[u] = v;
            if (dfs2(u, parent[u],adj))
                return true;
        } else if (color[u] == 1) {
            cycle_end = v;
            cycle_start = u;
            return true;
        }
    }
    color[v] = 2;
    return false;
}
signed  main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        vector<vector<int>> vs(n+1);
        bool* visited=new bool[n+1];
        int *degree=new int[n+1]();
        vector<int> cycle;
        for(int i=0;i<=n;i++)
        visited[i]=false;

        for(int i=0;i<n;i++)
        {
            int x,y;
            cin>>x>>y;
            degree[x]++;
            degree[y]++;
            vs[x].push_back(y);
            vs[y].push_back(x);
        }
        color.assign(n+1, 0);
        parent.assign(n+1, -1);
        cycle_start = -1;

            for (int v = 1; v <= n; v++) {
                if (color[v] == 0 && dfs2(v,parent[v],vs))
                    break;
            }

                cycle.push_back(cycle_start);
                for (int v = cycle_end; v != cycle_start; v = parent[v])
                    cycle.push_back(v);
                cycle.push_back(cycle_start);
                reverse(cycle.begin(), cycle.end());
        cycle.pop_back();
        vector<int> cycler;
        for(int g:cycle)
        {
            visited[g]=true;
        }
        for(int g:cycle)
        {

          cycler.push_back(1+dfs(g,visited,vs));
        }
        
        int total=permute(n,2);
        int q=cycler.size()-1;
        
        for(int i=q-1;i>=0;i--)
        {
            total+=cycler[i]*cycler[i+1];
            cycler[i]+=cycler[i+1];
            
            
        }
        cout<<total<<endl;
    }
}
