#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef pair<ll, ll>pll;
const int N = 2e5 + 5;
vector<int>g[N];
int tc;
bool cycle[N];
ll ans;
int n, sum[N];
vector<int>v;
bool vis[N], in_stack[N];
void init() {
    ans = 0;
    for (int i = 1; i <= n; ++i)
        g[i].clear(), in_stack[i] = vis[i] = cycle[i] = sum[i] = 0;
}
void dfs(int u, int p) {
    v.push_back(u);
    vis[u] = 1;
    in_stack[u] = 1;
    for (auto &c : g[u]) {
        if (c != p) {
            if (!vis[c])
                dfs(c, u);
            else if (in_stack[c]) {
                int cur = v.size() - 1;
                while (1) {
                    cycle[v[cur]] = 1;
                    if (v[cur] == c) break;
                    --cur;
                }
            }
        }
    }
    v.pop_back();
    in_stack[u] = 0;
}
int go(int u, int p) {
    sum[u] = 1;
    for (auto &c : g[u])
        if (c != p && !cycle[c])
            sum[u] += go(c, u);
    return sum[u];
}
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> tc;
    while (tc--) {
        cin >> n;
        init();
        for (int i = 0; i < n; ++i) {
            int u, v;
            cin >> u >> v;
            g[u].push_back(v);
            g[v].push_back(u);
        }
        dfs(1, 0);
        for (int i = 1; i <= n; ++i)
            if (cycle[i])
                go(i, 0);
        ans = n * 1LL * (n - 1);
        for (int i = 1; i <= n; ++i)
            if (cycle[i])
                ans -= (1LL * sum[i] * (sum[i] - 1)) / 2;
        cout << ans << '\n';
    }
    return 0;
}