/*
    +-----------------------+
    |       CHECKLIST       |
    +-----------------------+
    |1. PIGEONHOLE PRINCIPLE|
    |2. TWO POINTERS        |
    |3. BINARY SEARCH       |
    |4. GREEDY ALGORITHM    |
    |5. DYNAMIC PROGRAMMING |
    |6. GRAPH               |
    |7. SEGMENT TREE        |
    +-----------------------+

*/

#include <iostream>
#include <iomanip>
#include <cstring>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <list>
#include <set>
#include <utility>
#include <map>
#include <cmath>
#include <cassert>

using namespace std;

class Graph {
public:
	vector<vector<int> > adj_list;
	Graph(int n) : adj_list(vector<vector<int> > (n)) {}
	void add_edge(int u, int v, bool bidirectional = true) {
		adj_list[u].push_back(v);
		if (bidirectional) {
			adj_list[v].push_back(u);
		}
	}
};

void print_err() {
	cerr << "\n";
}

template <class T, class... Arg>
void print_err(T x, Arg&&... args) {
	cerr << x << " ";
	print_err(args...);
}

template<class T>
void print_container(T &cont) {
	for (auto iter : cont) {
		cerr << iter << " ";
	}
	cerr << "\n";
}

void in() {}

template<class T, class... Arg>
void in(T &x, Arg&&... args) {
	cin >> x;
	in(args...);
}

template<class T>
void in_c(T &container, int start, int end) {
	for (int i = start; i < end; ++i) {
		cin >> container[i];
	}
}

#ifdef local
#define debug(...) print_err(__VA_ARGS__)
#define debug_c(container) print_container(container)
#else
#define debug(...)
#define debug_c(container)
#endif

inline void kick_temp(int test) {
	cout << "Case #" << test << ": ";
}

#define test_case int test_cases;\
                cin>>test_cases;\
                for(i = 1; i<=test_cases;++i)
#define lu(var,l,r) for(var=l;var<r;++var)
#define ld(var,r,l) for(var=r;var>=l;--var)
#define ll long long
#define mp make_pair
#define pb push_back
#define v vector
#define vi vector<int>
#define vvi vector<vector<int> >
#define vll vector<ll>
#define vvll vector<vector<ll> >
#define vb vector<bool>
#define vvb vector<vector<bool> >
#define pii pair<int,int>
#define pll pair<ll,ll>
#define rev_sort(...) sort(__VA_ARGS__);reverse(__VA_ARGS__);
#define br cout<<"\n"
#define sp cout<<" "
#define pr cout<<
#define inp cin>>
#define ff first
#define ss second
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define all(A) (A).begin(),(A).end()
#define mod 1000000007
vi d4x {0, 0, 1, -1};
vi d4y{ -1, 1, 0, 0};
vi d8x{0 , 0, 1, -1, 1, 1, -1, -1};
vi d8y{1, -1, 0, 0, -1, 1, 1, -1};

bool dfs(int node, vb &visited, set<int> &cv, stack<int> &st, Graph &graph, int par) {
	visited[node] = true;
	st.push(node);
	for (int child : graph.adj_list[node]) {
		if (child == par) {
			continue;
		}
		if (!visited[child]) {
			if (dfs(child, visited, cv, st, graph, node)) {
				return true;
			}
		} else {
			while (st.top() != child) {
				cv.insert(st.top());
				st.pop();
			}
			cv.insert(st.top());
			return true;
		}
	}
	st.pop();
	return false;
}

ll get_nodes(int node, int par, Graph &graph, set<int> &cv) {
	ll count = 1;
	for (int child : graph.adj_list[node]) {
		if (child == par or cv.find(child) != cv.end()) {
			continue;
		}
		count += get_nodes(child, node, graph, cv);
	}
	return count;
}

void solve(int test) {
	debug("------------");
	int i, j, n;
	inp n;
	Graph graph = n;
	int u, v;
	lu(i, 0, n) {
		in(u, v);
		graph.add_edge(--u, --v);
	}
	::vector<bool> vis(n, false);
	set<int> cycles;
	stack<int> _stack;
	dfs(0, vis, cycles, _stack, graph, -1);
	debug_c(cycles);
	ll ans = 0;
	for (int node : cycles) {
		ll count = get_nodes(node, -1, graph, cycles);
		debug(node, count);
		ans += (count * (count - 1)) / 2 + count * (n - count);
	}
	pr ans;
	br;
}

int main() {
	int i = 1;
	fastio;
	test_case
	solve(i);
	return 0;
}