#include <bits/stdc++.h>
/** #include <ext/pb_ds/assoc_container.hpp>
 * #include <ext/pb_ds/tree_policy.hpp>
 * using namespace __gnu_pbds; */
using namespace std;

#define ll long long
#define ull unsigned long long
#define f(a, b) for (ll i = a; i < b; i++)
#define mod 1000000007
#define pb push_back
#define vll vector<ll>
#define pll vector<pair<ll, ll>>
#define ld long double
#define fr(a, b) for (ll j = a; j >= b; j--)
#define fi(a, b) for (ll j = a; j < b; j++)
#define fii(a, b) for (ll k = a; k < b; k++)
/** typedef tree<ll
 * ,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
 * ordered_set; */

template <class T> ostream &operator<<(ostream &os, vector<T> V) {
  os << "[ ";
  for (auto v : V)
    os << v << " ";
  os << "]";
  return os;
}
template <class T> ostream &operator<<(ostream &os, set<T> S) {
  os << "{ ";
  for (auto s : S)
    os << s << " ";
  return os << "}";
}
template <class L, class R> ostream &operator<<(ostream &os, map<L, R> M) {
  os << "{ ";
  for (auto m : M)
    os << "(" << m.first << ":" << m.second << ") ";
  return os << "}";
}
template <class L, class R> ostream &operator<<(ostream &os, pair<L, R> P) {
  return os << "(" << P.first << "," << P.second << ")";
}

const ll N = 200005;
vll adj[N];
ll n, color[N], parent[N], cycle_end, cycle_start, ans;
bool C[N];

bool dfs(ll v, ll par) {
  color[v] = 1;
  for (ll u : adj[v]) {
    if (u == par)
      continue;
    if (color[u] == 0) {
      parent[u] = v;
      if (dfs(u, parent[u]))
        return true;
    } else if (color[u] == 1) {
      cycle_end = v;
      cycle_start = u;
      return true;
    }
  }
  color[v] = 2;
  return false;
}

ll DFS(ll x, ll pr) {
  ll k = 1;
  f(0, adj[x].size()) {
    if (adj[x][i] != pr)
      k += DFS(adj[x][i], x);
  }
  return k;
}

void solve() {
  cycle_start = -1;
  for (int v = 1; v <= n; v++) {
    if (color[v] == 0 && dfs(v, parent[v]))
      break;
  }
  vector<int> cycle;
  C[cycle_start] = 1;
  cycle.push_back(cycle_start);
  for (int v = cycle_end; v != cycle_start; v = parent[v])
    cycle.push_back(v), C[v] = 1;
  vll V;
  f(0, cycle.size()) {
    ll v = cycle[i];
    ll tot = 0;
    fi(0, adj[v].size()) {
      if (!C[adj[v][j]]) {
        tot += DFS(adj[v][j], v);
      }
    }
    V.pb(tot);
  }
  ll l = cycle.size();
  ans += l * (l - 1);
  f(0, V.size()) {
    ll k = V[i];
    ans += k * (l - 1) * 2 + k;
    ans += k * (k - 1) / 2;
  }
  ll sum = 0;
  f(0, V.size()) sum += V[i];
  f(0, V.size()) {
    sum -= V[i];
    ans += V[i] * sum * 2;
  }
}

int main() {
#ifndef ONLINE_JUDGE
  freopen("input.txt", "rt", stdin);
  freopen("output.txt", "wt", stdout);
#endif
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  ll t;
  cin >> t;
  while (t--) {
    cin >> n;
    ans = 0;
    f(1, n + 1) adj[i].clear(), color[i] = 0, parent[i] = -1, C[i] = false;
    f(0, n) {
      ll x, y;
      cin >> x >> y;
      adj[x].pb(y);
      adj[y].pb(x);
    }
    solve();
    cout << ans << '\n';
  }

#ifndef ONLINE_JUDGE
  cout << "\nTime Elapsed : " << 1000 * (ld)clock() / (ld)CLOCKS_PER_SEC
       << " ms\n";
#endif
  return 0;
}