#include <bits/stdc++.h>
using namespace std;

int n;

vector <int> v[200005];

void erase(vector <int> &vec, int val)
{
    for(int i = 0; i < vec.size(); i++)
        if(vec[i] == val)
            vec.erase(vec.begin() + i, vec.begin() + i + 1);
}

int main()
{
    int t;

    cin >> t;

    while(t--)
    {
        cin >> n;

        for(int i = 1; i <= n; i++)
        {
            int x, y;

            cin >> x >> y;

            v[x].push_back(y);
            v[y].push_back(x);
        }

        queue <int> leafs;

        for(int i = 1; i <= n; i++)
            if(v[i].size() == 1)
                leafs.push(i);

        int tree_size[200005];

        for(int i = 1; i <= n; i++)
            tree_size[i] = 1;

        while(!leafs.empty())
        {
            int leaf_current = leafs.front();

            leafs.pop();

            int dad = v[leaf_current][0];

            tree_size[dad] += tree_size[leaf_current];
            tree_size[leaf_current] = 0;

            v[leaf_current].clear();
            erase(v[dad], leaf_current);

            if(v[dad].size() == 1)
                leafs.push(dad);
        }

        long long ans = 0;

        for(int i = 1; i <= n; i++)
            ans += 1LL * tree_size[i] * (tree_size[i] - 1) / 2 +
                   1LL * tree_size[i] * (n - tree_size[i]);

        for(int i = 1; i <= n; i++)
            v[i].clear();

        cout << ans << '\n';
    }

    return 0;
}
