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

#define ff    first
#define ss    second
#define pb    push_back

typedef long long    ll;
typedef pair<ll,ll>    ii;
typedef long double    lf;


mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll SQ = 320;
const ll N = 6e5+5;
const ll mod = 998244353;

int bit[N];
vector <int> g[N];
int tme = 0;
int tin[N], tout[N];
int fat[N];

void update (int i, int x) {
  for (++i; i < N; i += (i & (-i))) bit[i] += x;
}

int query (int i) {
  int sum = 0;
  for (++i; i > 0; i -= (i & (-i))) sum += bit[i];
  return sum;
}

int query (int i, int j) {
  return query (j) - query (i - 1);
}

void dfs (int u, int p) {
  tin[u] = tme++;
  fat[u] = p;
  for (auto &v : g[u]) {
    if (v == p) continue;
    dfs(v, u);
  }
  tout[u] = tme++;
}

ll solve (int l, int r) {
  if (l > r) { return 0; }
  if (l == r) { return 1; }
  int m = (l + r) / 2;

  ll cost = 0;
  vector <int> val(r - l + 1);
  vector <int> valid(r - l + 1);
  val[m - l] = m;
  valid[m - l] = 1;
//  cout << "mid " << m << endl;

  {
    vector <int> upds;
    update(tin[m], 1);
    upds.pb(tin[m]);
    int mn = m;
    int mx = m;
    for (int i = m + 1; i <= r; ++i) {
        int lst = -1;

//      cout << "adding " << i << " to path" << endl;
      int rep = i;
      while (query(tin[rep], tin[rep]) == 0) {
//        cout << rep << endl;
        update(tin[rep], 1);
        upds.pb(tin[rep]);
        mn = min(mn, rep);
        mx = max(mx, rep);
        if (mn < l) break;
        if (mx > r) break;
        int inn = 0;
        for (auto &v : g[rep]) {
          if (query(tin[v], tout[v]) && v != fat[rep] && v != lst) {
            lst=rep;
            rep = v;
            inn = 1;
            break;
          }
        }
        if (!inn) lst=rep, rep = fat[rep];
      }
      val[i - l] = mn;
      if (mx <= i) valid[i - l] = 1;
    }

    for (auto &e : upds) update(e, -1);
  }
//  cout << "pass " << endl;
  {
    vector <int> upds = {tin[m]};
    update(tin[m], 1);
    int mx = m;
    int mn = m;
    for (int i = m - 1; i >= l; --i) {
      int rep = i;
      //cout << "adding " << i << '\n';
        int lst = -1;
      while (query(tin[rep], tin[rep]) == 0) {
        update(tin[rep], 1);
        upds.pb(tin[rep]);
        mx = max(mx, rep);
        mn = min(mn, rep);
        //cout << rep << '\n';
        if (mx > r) break;
        if (mn < l) break;
        int inn = 0;
        for (auto &v : g[rep]) {
          if (query(tin[v], tout[v]) && v != fat[rep] && v!=lst) {
            lst = rep;
            rep = v;
            inn = 1;
            break;
          }
        }
        if (!inn) lst = rep, rep = fat[rep];
      }
      val[i - l] = mx;
      if (mn >= i) valid[i - l] = 1;
    }

    for (auto &e : upds) update(e, -1);
  }

//  cout << "pass " << endl;

  vector <int> sufsum(r - l + 2);
  for (int i = r; i >= l; --i) sufsum[i - l] = sufsum[i - l + 1] + valid[i - l];

  int idx = m;
  int idx2 = m;
  for (int i = m; i >= l; --i) {
    while (idx <= r && val[idx - l] >= i) idx++;
    while (idx2 <= r && val[i - l] > idx2) idx2++;
//    cout << i << ' ' << idx - idx2 << '\n';
    if (valid[i - l]) {

      cost += max(0ll, 1ll * sufsum[idx2 - l] - sufsum[idx - l]);
    }
  }
//  cout << "-pass " << endl;
 // cout << l << ' ' << m << ' '<< r << ' ' << cost << endl;
 // for (auto &e : val) cout << e << ' ';
 // cout << endl;
 // for (auto &e : valid) cout << e << ' ';
 // cout << endl;

  return cost + solve(l, m - 1) + solve(m + 1, r);
}

int main(){
  #ifdef LOCAL
  freopen("input.txt","r",stdin);
  #endif // LOCAL
  ios_base::sync_with_stdio(0);
  cin.tie(0);cout.tie(0);

  int t; cin >> t;
  while (t--) {
    int n; cin >> n;
    for (int i = 0; i < n; ++i) g[i].clear();
    for (int i = 0; i + 1 < n; ++i) {
      int u, v; cin >> u >> v;
      u--;v--;
      g[u].pb(v);
      g[v].pb(u);
    }
    dfs(0, -1);
    cout << solve(0, n - 1) << '\n';
  }
  return 0;
}