#include<bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define vll vector<ll>
#define eb emplace_back
#define pb push_back
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define sz(v) ((int)v.size())
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define umap unordered_map
#define uset unordered_set
#define mset multiset
#define ui unsigned int
#define ull unsigned ll
#define i128 __int128
using namespace std;

namespace qiqi {
	const int inf = 1e9;
	struct Seg {
#define ls (x<<1)
#define rs (ls|1)
		int n; vi mx,cnt,tag;
		Seg(int n):n(n),mx(n*4,-inf),cnt(n*4),tag(n*4) {}
		void pull(int x) {
			mx[x] = max(mx[ls],mx[rs]);
			cnt[x] = 0;
			if (mx[x] == mx[ls]) {
				cnt[x] += cnt[ls];
			}
			if (mx[x] == mx[rs]) {
				cnt[x] += cnt[rs];
			}
		}
		void apl(int x,int k) {
			mx[x] += k; tag[x] += k;
		}
		void push(int x) {
			if (tag[x]) {
				apl(ls,tag[x]); apl(rs,tag[x]);
				tag[x] = 0;
			}
		}
		void ins(int x,int l,int r,int p,int k) {
			if (r-l == 1) {
				mx[x] = k; cnt[x] = 1;
				return;
			}
			int mid = l+((r-l)>>1);
			push(x);
			if (p < mid) {
				ins(ls,l,mid,p,k);
			}
			else {
				ins(rs,mid,r,p,k);
			}
			pull(x);
		}
		void ins(int p,int k) {
			return ins(1,0,n,p,k);
		}
		void upd(int x,int l,int r,int pl,int pr,int k) {
			if (pl <= l && r <= pr) {
				return apl(x,k);
			}
			int mid = l+((r-l)>>1);
			push(x);
			if (pl < mid) {
				upd(ls,l,mid,pl,pr,k);
			}
			if (pr > mid) {
				upd(rs,mid,r,pl,pr,k);
			}
			pull(x);
		}
		void upd(int pl,int pr,int k) {
			return upd(1,0,n,pl,pr,k);
		}
	};
	void main() {
		int n;
		cin >> n;
		vector<vi> e(n);
		for (int i = 0; i < n-1; i++) {
			int u,v;
			cin >> u >> v; u--; v--;
			if (u > v) {
				swap(u,v);
			}
			e[u].eb(v);
		}
		Seg seg(n);
		ll ans = 0;
		for (int i = n-1; i >= 0; i--) {
			seg.ins(i,-i);
			for (auto x:e[i]) {
				seg.upd(x,n,1);
			}
			if (seg.mx[1] == -i) {
				ans += seg.cnt[1];
			}
		}
		cout << ans << '\n';
	}
}

int main() {
//	clock_t st = clock();
//	freopen("test.in","r",stdin);
//	freopen("test.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int T = 1;
	cin >> T;
	while (T--) {
		qiqi::main();
	}

//	cout << (double)(clock()-st)/CLOCKS_PER_SEC;
	return 0;
}