#include <bits/stdc++.h>
using namespace std;
bool stB;
namespace SOL {

void debug(const char *msg, ...) {
#ifdef CLESIP
    va_list arg;
    static char pbString[512];
    va_start(arg,msg);
    vsprintf(pbString,msg,arg);
    cerr << "[DEBUG] " << pbString << "\n";
    va_end(arg);
#endif    
}

#define PASSED cerr << "PASSED " << __FUNCTION__ << " #" << __LINE__ << "\n";

using i64 = long long;
using i128 = __int128_t;
template <typename T, typename L> void chkmax(T &x, L y) { if (x < y) x = y; }
template <typename T, typename L> void chkmin(T &x, L y) { if (y < x) x = y; }

const int N = 3e5 + 10;

namespace LazySegmentTree {
	const int SEG_SIZE = N * 4;
	template<typename Node, typename Tag>
	struct LazyTagSegTree {
		#define lc (x * 2)
		#define rc (x * 2 + 1)
		#define mid ((l + r) >> 1)

		Node dat[SEG_SIZE];
		Tag tag[SEG_SIZE];

		void pull(int x) {
			dat[x] = dat[lc] + dat[rc];
		}

		void apply(int x, const Tag &t, int sze) {
			dat[x].apply(t, sze);
			tag[x].apply(t);
		}

		void push(int x, int l, int r) {
			if (tag[x]) {
				apply(lc, tag[x], mid - l + 1);
				apply(rc, tag[x], r - mid);
				tag[x].clear();
			}
		}

		void build(int x, int l, int r) {
			tag[x].clear();
			if (l == r) {
				dat[x].init(l);
				return;
			}
			build(lc, l, mid);
			build(rc, mid + 1, r);
			pull(x);
		}

		Node query(int x, int l, int r, int ql, int qr) {
			if (ql <= l && r <= qr) 
				return dat[x];
			push(x, l, r);
			if (ql <= mid && mid < qr)
				return query(lc, l, mid, ql, qr) + query(rc, mid + 1, r, ql, qr);
			else if (ql <= mid)
				return query(lc, l, mid, ql, qr);
			else
				return query(rc, mid + 1, r, ql, qr);
		}

		void modify(int x, int l, int r, int ql, int qr, const Tag &t) {
			if (ql > qr)
				return;
			if (ql <= l && r <= qr) 
				return apply(x, t, r - l + 1);
			push(x, l, r);
			if (ql <= mid)
				modify(lc, l, mid, ql, qr, t);
			if (mid < qr)
				modify(rc, mid + 1, r, ql, qr, t);
			pull(x);
		}

		void change(int x, int l, int r, int pos, const Node &k) {
			if (l == r)
				return dat[x] = k, void();
			push(x, l, r);
			if (pos <= mid)
				change(lc, l, mid, pos, k);
			else
				change(rc, mid + 1, r, pos, k);
			pull(x);
		} 

		#undef lc
		#undef rc
		#undef mid
	};
}

struct Tag {
	int add;

	void apply(const Tag &o) {
		add = add + o.add;
	}

	void clear() {
		add = 0;
	}

	operator bool () const {
		return add;
	}
};

struct Node {
	int mn, cnt;

	void init(int p) {
		mn = 0, cnt = 1;		
	}

	void apply(const Tag &o, int size) {
		mn += o.add;
	}
};

Node operator + (const Node &lhs, const Node &rhs) {
	if (lhs.mn == rhs.mn)
		return { lhs.mn, lhs.cnt + rhs.cnt };
	if (lhs.mn < rhs.mn)
		return lhs;
	else
		return rhs;
}

LazySegmentTree::LazyTagSegTree<Node, Tag> segt; 
int n;
vector<int> G[N];

void ___solve() {
	
	cin >> n;
	for (int i = 1; i <= n; i ++)
		G[i].clear();
	for (int i = 1, x, y; i < n; i ++) {
		cin >> x >> y;
		if (x > y)
			swap(x, y);
		G[y].push_back(x);
	}
	segt.build(1, 1, n);
	i64 ans = 0;
	for (int i = 1; i <= n; i ++) {
		segt.modify(1, 1, n, 1, i, { 1 });
		for (int j : G[i])
			segt.modify(1, 1, n, 1, j, { -1 });
		auto res = segt.query(1, 1, n, 1, i);
		if (res.mn == 1) {
			ans += res.cnt;
		}
	}
	cout << ans << "\n";
}

}
bool edB;
signed main() {
	// cerr << "Memory: " << (&stB - &edB) / 1024.0 / 1024.0 << "MB\n";
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	int tt; cin >> tt;
	while (tt --) 
		SOL::___solve();
	return 0;
}