#include <bits/stdc++.h>
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("-funroll-loops")
using namespace std;
using ll=long long;
using ull=unsigned long long;
//#define mid ((l+r)>>1)
//#define len (r-l+1)
//#define ls p<<1
//#define rs p<<1|1
//#define int long long
constexpr int inf=1e9+7;
constexpr int mod=998244353;
//constexpr ll inf=1e18+7;
constexpr int N=300005;

struct node
{
    int to,nxt;
}
e[N<<1];
int tot,head[N];

int t,n;
int son[N],siz[N],f[N][20],son2[N],son3[N],siz2[N],pre[N],pre1[N];
ll ans;
void add(int u,int v)
{
    e[++tot].to=v;
    e[tot].nxt=head[u];
    head[u]=tot;
}

void dfs1(int x,int fa)
{
    siz[x]=1;
    pre[x]=fa;
    for(int i=head[x];i;i=e[i].nxt)
    {
        int v=e[i].to;
        if(v==fa)continue;
        dfs1(v,x);
        siz[x]+=siz[v];
        if(siz[v]>siz[son[x]])
        {
            son2[x]=son[x];
            son[x]=v;
        }
        else if(siz[v]>siz[son2[x]])
        {
            son2[x]=v;
        }
    }
    //倍增跳儿子
    f[x][0]=son[x];
    for(int i=1;i<=20;++i)
    {
        f[x][i]=f[f[x][i-1]][i-1];
    }
}

int jump(int x,int res)
{
    return x*(max(siz2[son3[x]],res-siz2[x])<=res/2);
}

void dfs2(int x,int fa)
{
    for(int i=head[x];i;i=e[i].nxt)
    {
        //换根
        int v=e[i].to;
        if(v==fa)continue;
        siz2[x]=siz[1]-siz[v];
        pre1[v]=pre1[x]=0;

        if(son[x]==v) son3[x]=son2[x];
        else son3[x]=son[x];
        if(siz2[fa]>siz2[son3[x]]) son3[x]=fa;
        f[x][0]=son3[x];
        for(int j=1;j<=20;++j) f[x][i]=f[f[x][j-1]][j-1];
        int b=x;
        for(int j=20;j>=0;--j) 
        {
            if(siz2[x]-siz2[f[b][j]]<=siz2[x]/2)
            {
                b=f[b][j];
            }
        }
        ans+=jump(son3[b],siz2[x])+jump(b,siz2[x])+jump(pre1[b],siz2[x]);
        b=v;
        for(int j=20;j>=0;--j) 
        {
            if(siz2[v]-siz2[f[b][j]]<=siz2[v]/2)
            {
                b=f[b][j];
            }
        }
        ans+=jump(son3[b],siz2[v])+jump(b,siz2[v])+jump(pre1[b],siz2[v]);
        pre1[x]=v;
        dfs2(v,x);
    }
    son3[x]=f[x][0]=son[x];
    pre1[x]=pre[x];
    for(int i=1;i<=20;++i)
    {
        f[x][i]=f[f[x][i-1]][i-1];
    }
    siz2[x]=siz[x];
}

// char buf[1<<21],*p1,*p2;
// #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}
void wt(long long x,char ch=0){if(x<0) putchar('-'),wt(-x);else{if(x>=10) wt(x/10);putchar(x%10+'0');}if(ch) putchar(ch);return;}
signed main(){
    //freopen("in.in","r",stdin);
    //freopen("ot.out","w",stdout);
    cin.tie(0);
    cout.tie(0);
    t=read();
    while(t--)
    {
        memset(head,0,sizeof(head));
        memset(pre,0,sizeof(pre));
        memset(pre1,0,sizeof(pre1));
        memset(son,0,sizeof(son));
        tot=0,ans=0;
        n=read();
        for(int i=1;i<n;++i)
        {
            int u=read(),v=read();
            add(u,v);
            add(v,u);
        }
        dfs1(1,0);
        for(int i=1;i<=n;++i)
        {
            siz2[i]=siz[i];
            son3[i]=son[i];
            pre1[i]=pre[i];
        }
        dfs2(1,0);
        wt(ans,'\n');
    }
    // cout<<clock()/(double)CLOCKS_PER_SEC;
    fclose(stdin);
    fclose(stdout);
    return 0;
}