#include<bits/stdc++.h>

#define int int64_t
#define endl '\n'
#define fast ios_base::sync_with_stdio(false); cin.tie(0);
#define FOR(i,l,r) for(int i = l; i < r; i++)
#define ROF(i,l,r) for(int i = r - 1; i >= l; i--)
using namespace std;

const int INF = 1e9 - 1;

int32_t main(){
    fast;
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        vector<set<int> > g(n);

        for(int i = 0; i < n; i++){
            int x, y;
            cin >> x >> y;
            x--;
            y--;
            g[x].insert(y);
            g[y].insert(x);
        }

        vector<int> vals(n, 1);
        queue<int> leave;

        for(int i = 0; i < n; i++) if(g[i].size() == 1) leave.push(i);

        while(!leave.empty()){
            int v = leave.front();
            leave.pop();
            int to = *g[v].begin();
            vals[to] += vals[v];
            vals[v] = 0;
            g[v].clear();
            g[to].erase(v);
            if(g[to].size() == 1) leave.push(to);
        }

        int ans = 0;

        for(int i = 0; i < n; i++){
            ans += vals[i] * (n - vals[i]);
            ans += (vals[i] * (vals[i] - 1)) / 2;
        }

        cout << ans << endl;

    }


}
