#include <cstdio>
#include <cctype>

template <typename T> T read() {
  T res = 0, f = 1;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) res = (res << 3) + (res << 1) + (ch ^ 48);
  return res * f;
}

void write(__int128 x, char ed = '\n') {
  if (x < 0) x = -x, putchar('-');
  static int sta[64], top = 0;
  do {
    sta[++top] = x % 10;
    x /= 10;
  } while (x);
  while (top) {
    putchar(sta[top--] ^ 48);
  }
  putchar(ed);
}

template <typename T> void write(T x, char ed = '\n') {
  write((__int128)x, ed);
}

int n;
void work() {
  n = read<int>();
  for (int i = 1; i <= n - 1; ++i) {
    read<int>(), read<int>();
  }
  
  long long ans = 0;
  for (int i = 1; i <= n - 1; ++i) {
    // 1--i, i+1--n
    if (i & 1) {
      ans += (1 + i) / 2;
    } else {
      ans += (1 + i) / 2 + (1 + i) / 2 + 1;
    }
    if ((n - (i + 1) - 1) & 1) {
      ans += (i + 1 + n) / 2;
    } else {
      ans += (i + 1 + n) / 2 + (i + 1 + n) / 2 + 1;
    }
  }

  write(ans);
}

int main() {
  #ifdef LOCAL
    freopen("!input.in", "r", stdin);
    freopen("!output.out", "w", stdout);
  #else
   freopen("centroid.in", "r", stdin);
   freopen("centroid.out", "w", stdout);
  #endif

  int T = read<int>();
  while (T--) {
    work();
  }
  return 0;
}