#include <iostream>
#include <fstream>
#include <list>
#include <stack>
#include <deque>
#include <utility>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <vector>
#include <cmath>
#include <string>
#include <algorithm>
#include <iomanip>
#include <ctime>
#include <iterator>
#include <cstdio>
#include <cstring>
#include <cstdlib>


using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

#define f first
#define s second
#define pb push_back
#define mp make_pair

const int maxn = 1000500;
const int inf = 2e9;
const double eps = 1e-8;
const int base = 1073676287;

vector < int > edge[maxn];
int used[maxn];
// int timer;
// int anc[maxn];
// int SZ[maxn];

// void dfsBrute( int v, int l, int r ) {
// 	used[v] = true;
// 	int sz = edge[v].size();
// 	for ( int j = 0; j < sz; j++ ) {
// 		int to = edge[v][j];
// 		if ( used[to] )
// 			continue;
// 		if ( to > r || to < l )
// 			continue;
// 		dfsBrute( to, l, r );
// 	}
// }

// bool correct( int n, int l, int r ) {
// 	timer = 0;
// 	for ( int j = l; j <= r; j++ )
// 		used[j] = 0;
// 	for ( int j = l; j <= r; j++ )
// 		if ( !used[j] ) {
// 			++timer;
// 			if ( timer == 2 )
// 				return false;
// 			dfsBrute( j, l, r );
// 		}
// 	return true;
// }

// ll brute( int n ) {
// 	ll ans = 0;
// 	for ( int j = 1; j <= n; j++ )
// 		for ( int i = 1; i <= j; i++ )
// 			ans += correct( n, i, j );
// 	return ans;
// }

// int findSet( int v ) {
// 	return v == anc[v] ? v : anc[v] = findSet( anc[v] );
// }

// void uniteSets( int u, int v ) {
// 	u = findSet( u );
// 	v = findSet( v );
// 	if ( SZ[u] < SZ[v] )
// 		swap( u, v );
// 	SZ[u] += SZ[v];
// 	anc[v] = u;
// }

ll ans;
int low[maxn];
int high[maxn];
int prefSum[maxn];

void dfs( int v, int anc, int l, int r ) {
	for ( int to : edge[v] ) {
		if ( used[to] )
			continue;
		if ( to == anc )
			continue;
		if ( to < l || to > r )
			continue;
		low[to] = min( to, low[v] );
		high[to] = max( to, high[v] );
		dfs( to, v, l, r );
	}
}

inline int getSum( int l, int r ) {
	return l > r ? 0 : prefSum[r] - prefSum[l - 1];
}

inline void solution( int l, int r ) {
    if ( l > r )
        return;
	int center = ( l + r ) >> 1;
	for ( int j = l; j <= r; j++ ) {
		low[j] = -inf;
		high[j] = inf;
	}
	low[center] = high[center] = center;
	dfs( center, -1, l, r );
	for ( int j = center - 1; j >= l; j-- ) {
		low[j] = min( low[j], low[j + 1] );
		high[j] = max( high[j], high[j + 1] );
	}
	for ( int j = center + 1; j <= r; j++ ) {
		low[j] = min( low[j], low[j - 1] );
		high[j] = max( high[j], high[j - 1] );
	}
	prefSum[center - 1] = 0;
	prefSum[center] = 1;
	for ( int j = center + 1; j <= r; j++ )
		prefSum[j] = prefSum[j - 1] + ( high[j] == j );

	int R = center;
	for ( int j = center; j >= l; j-- ) {
		if ( low[j] != j )
			continue;
		while ( R <= r && low[R] >= j )
			++R;
		ans += 1LL * getSum( high[j], R - 1 );
	}
	used[center] = true;
	if ( l != r ) {
		solution( l, center - 1 );
		solution( center + 1, r );
	}
}

int main()
{
    srand( time( NULL ) );
    // freopen( "input.txt", "r", stdin );
    // freopen( "output.txt", "w", stdout );
    // ios_base::sync_with_stdio(false);


    int q;
    scanf ( "%d", &q );
    while ( q-- ) {
    	int n;
    	scanf ( "%d", &n );
    	for ( int j = 1; j < n; j++ ) {
    		int u, v;
    		scanf ( "%d%d", &u, &v );
    		edge[u].pb( v );
    		edge[v].pb( u );
    	}
    	for ( int j = 1; j <= n; j++ )
    		used[j] = false;
    	ans = 0LL;
    	solution( 1, n );
    	for ( int j = 1; j <= n; j++ )
    		edge[j].clear();
    	cout << ans << endl;
    }


    // int it = 50000;
    // int maxN = 10;
    // for ( int qqq = 1; qqq <= it; qqq++) {
    // 	int n = 1 + rand() % maxN;
    // 	for ( int j = 1; j <= n; j++ ) {
    // 		edge[j].clear();
    // 		anc[j] = j;
    // 		SZ[j] = 1;
    // 		used[j] = false;
    // 	}
    // 	for ( int j = 1; j < n; j++ ) {
    // 		int u = 1 + rand() % n;
    // 		int v = 1 + rand() % n;
    // 		while ( findSet( u ) == findSet( v ) ) {
    // 			u = 1 + rand() % n;
    // 			v = 1 + rand() % n;
    // 		}
    // 		edge[u].pb( v );
    // 		edge[v].pb( u );
    // 		uniteSets( u, v );
    // 	}
    // 	ans = 0;
    // 	solution( 1, n );

    // 	if ( brute( n ) != ans ) {
    // 		puts( "kek" );
    // 		printf( "%d\n", n );
    // 		for ( int j = 1; j <= n; j++ )
    // 			for ( int i : edge[j] )
    // 				if ( j < i )
    // 					printf( "%d %d\n", j, i );
    // 		printf( "\n" );
    // 		cout << brute( n ) << ' ' << ans << endl;
    // 		return 0;
    // 	}
    // 	// if ( qqq % ( it / 100 ) == 0 )
    // 	// 	printf( "%d%\n", qqq / ( it / 100 ) );
    // }
    // puts( "all good" );
    return 0;
}