#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int N = 200005;

vector<int> adj[N];

bool isCycle[N];
int par[N];
int depth[N];


void dfs(int node,int p) {
    depth[node] = depth[p] + 1;
    par[node] = p;
    
    for(int ch : adj[node]) {
        if(ch==p) {
            continue;
        }
        if(depth[ch]!=0 ) {
            if(depth[ch]<depth[node]) {
                int cur = node;

                while(true) {
                    isCycle[cur] = true;
                    if(cur==ch) {
                        break;
                    }
                    cur = par[cur];
                }
            }
            
        } else {
            dfs(ch,node);
        }
    }
}

int dfs2(int node,int p) {
    int ret = 1;
    for(int ch : adj[node]) {
        if(isCycle[ch] || ch==p) {
            continue;
        }
        ret += dfs2(ch,node);
    }
    return ret;
}

void solve2() {
    int n;
    scanf("%d",&n);
    for(int i=n;i;--i) {
        adj[i].clear();
        isCycle[i] = false;
        depth[i] = 0;
    }
    for(int i=0;i<n;++i) {
        int x,y;
        scanf("%d %d",&x,&y);
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    dfs(1,0);
    int cycleLen = 0;
    vector<int> v;
    for(int i=n;i;--i) {
        if(isCycle[i]) {
            ++cycleLen;
            
            int g = dfs2(i,0)-1;

            if(g!=0) {
                v.push_back(g);
            }
        }
    }
    ll ret = 0,sum = 0;
    for(int a : v) {
        sum += a;
    }
    
    for(int a: v) {
        ret += (ll)a*(a-1)/2;
        ret += (ll)a*(cycleLen)*2;
        ret += (ll)a*(sum-a);
        ret-=a;
    }

    ret += (ll)cycleLen*(cycleLen-1);
    printf("%lld\n",ret);
}

void solve() {
    int n;
    scanf("%d",&n);
    while(n--) {
        solve2();
    }
}

int main() {
	//freopen("sample_input.txt", "r", stdin);
	solve();
	return 0;
}
