#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;

#define re return
#define rep(i, n) for (int i = 0; i < n; ++i)
#define rrep(i, n) for (int i = n - 1; i >= 0; --i)
#define all(n) n.begin(), n.end()
#define rall(n) n.rbegin(), n.rend()
#define fi first
#define se second
#define sz(n) int(n.size())
#define sqr(n) ((n) * (n))


typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef long double ld;
typedef pair<int, int> pii;


void GO() {
#ifdef LOL
    freopen("../input.txt", "r", stdin);
    freopen("../output.txt", "w", stdout);

#endif
//    freopen("area.in", "r", stdin);
//    freopen("area.out", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0),     cout.tie(0);
}

const int INF = int(1e9) + 1;
//const ll mod = (int)1e9 + 7;
const int MAX_N = (int) 1e6 + 200000;

///var
//

void solve(){
    int n; cin >> n;
    vector<set<int> > g(n);
    rep(i, n){
        int a, b; cin >> a >> b; a--, b--;
        g[a].insert(b), g[b].insert(a);
    }
    deque<int> d;
    rep(i, n) if (sz(g[i]) == 1) d.push_back(i);
    ll ans = 0;
    vll cnt(n, 1);
    while(sz(d)){
        int v = *d.begin(); d.pop_front();
        int to = *g[v].begin();
        cnt[to] += cnt[v], cnt[v] = 0;
        g[v].clear(), g[to].erase(v);
        if (sz(g[to]) == 1) d.push_back(to);
    }
    rep(i, n) ans += cnt[i] * (cnt[i] - 1) / 2 + cnt[i] * (n - cnt[i]);
    cout << ans << '\n';
}
///ПОБЕД МУНИЦИПA
signed main() {
    GO(); int Q = 1; cin >> Q;
    while (Q--) solve();
}
///ФИОЛ