#include <bits/stdc++.h>
#define  lowbit(x)  x & (-x)
#define  mes(a, b)  memset(a, b, sizeof a)
#define  fi         first
#define  se         second
#define  pb         push_back
#define  pii        pair<int, int>
 
typedef unsigned long long int ull;
typedef long long int ll;
const int    maxn = 1e6 + 10;
const int    maxm = 1e5 + 10;
const ll     mod  = 1e9 + 7;
const ll     INF  = 1e18 + 100;
const int    inf  = 0x3f3f3f3f;
const double pi   = acos(-1.0);
const double eps  = 1e-8;
using namespace std;

int T;
int n;
vector<int> e[maxn];
ll siz[maxn],ans, dep[maxn],vis[maxn], flag, fa[maxn];
void dfs1(int u, int f, int d) {
    dep[u] = d;
    fa[u] = f;
    for(auto v : e[u]) {
        if(v == f) continue;
        if(dep[v]) {
            int x = u;
            vis[v] = 1;
            while(!vis[x]) {
                vis[x] = 1;
                x = fa[x];
               // printf("u = %d, x = %d, v = %d\n",u, x, v);
            }
            flag = 1;
        }
        if(flag) return;
        dfs1(v, u, d+1);
    }
}
void dfs(int u, int f) {
    siz[u] = 1;
    for(auto v : e[u]) {
        if(vis[v] || v == f) continue;
        dfs(v, u);
        siz[u] += siz[v];
    }
}
int main() {
    scanf("%d",&T);
    while(T--) {
        scanf("%d", &n);
        for(int i = 1;i <= n; i++) e[i].clear(), vis[i] = dep[i] = 0;
        for(int i = 1, u, v; i <= n; i++) {
            scanf("%d%d",&u, &v);
            e[u].pb(v); e[v].pb(u);
        }
        ans = flag = 0;
        dfs1(1, 1, 1);
        for(int i = 1; i <= n; i++) {
            if(vis[i]){
                dfs(i, i);
                ans += siz[i] * (siz[i] - 1) / 2 + siz[i] * (n-siz[i]) ;
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}