#include "bits/stdc++.h"
#undef DEBUG
#ifdef DEBUG
#include "PrettyDebug.hpp"
#else
#define debug(...) [](auto...){}(__VA_ARGS__)
#define debuga(...) [](auto...){}(__VA_ARGS__)
#endif
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Rev(i,a,b) for(int i=a;i>=b;i--)
#define Fin(file) freopen(file,"r",stdin)
#define Fout(file) freopen(file,"w",stdout)
using namespace std; typedef long long ll;
namespace FastIO{
    const int BUF_SIZ=1<<16;
    char in_buf[BUF_SIZ],*got_pos=in_buf,*read_pos=in_buf,out_buf[BUF_SIZ],*write_pos=out_buf;
    inline char get_next_char(){if(read_pos==got_pos){got_pos=read_pos=in_buf;got_pos+=fread(got_pos,sizeof(char),BUF_SIZ,stdin);}return*(read_pos++);}
    inline void flush_output(){fwrite(out_buf,sizeof(char),write_pos-out_buf,stdout);write_pos=out_buf;}
    inline void put_char(char ch){*(write_pos++)=ch;if(write_pos==out_buf+BUF_SIZ)flush_output();}
#ifndef FASTIO_READ_NEGATIVE
    template<typename T> inline void read(T& res){char ch;while(!isdigit(ch=get_next_char()));res=ch^'0';while(isdigit(ch=get_next_char()))res=(res<<3)+(res<<1)+(ch^'0');}
#else
    template<typename T> inline void read(T& res){char ch;bool flg=0;while(!isdigit(ch=get_next_char()))flg|=ch=='-';res=ch^'0';while(isdigit(ch=get_next_char()))res=(res<<3)+(res<<1)+(ch^'0');if(flg)res=-res;}
#endif
    template<typename T> inline void write(T x){if(!x){put_char('0');return;}static int lis[25],*lp=lis;while(x){*(++lp)=x%10;x/=10;}while(lp!=lis)put_char((*(lp--))+'0');}
    template<typename T> inline void writeln(const T& x){write(x);put_char('\n');}
    template<typename T> inline void writesp(const T& x){write(x);put_char(' ');}
    class _IO_Flusher{public:~_IO_Flusher(){flush_output();}}__Flusher;
    class IStream{public:
        template<typename T> inline IStream& operator>>(T& x){read(x);return *this;}
        inline IStream& operator>>(char* str){char ch;while(isspace(ch=get_next_char()));(*(str++))=ch;while(!isspace(ch=get_next_char())){if(ch==EOF)break;(*(str++))=ch;}*str=0;return *this;}
    }Cin;
    class OStream{public:
        template<typename T> inline enable_if_t<is_integral<T>::value,OStream&> operator<< (const T& x){write(x);return *this;}
        inline OStream& operator<< (const char& ch){put_char(ch);return *this;}
        inline OStream& operator<< (const char* str){for(const char* p=str;*p;put_char(*(p++)));return *this;}
    }Cout;
}
using namespace FastIO;
#define cin Cin
#define cout Cout
constexpr int N=5e5+5;
int n,D,ban[N],cursiz,siz[N],dep[N],son[N],pool[N],*ptr,*f[N]; ll ans,tmp[N],c1[N],c2[N],s1[N],s2[N]; vector<int> to[N];
inline bool ckmax(int& x,int y) { return x<y?x=y,true:false; }
pair<int,int> dfs1(int u,int pa){
    pair<int,int> res(1e9,0);
    int mx=0; siz[u]=1; for(int v:to[u]) if(v!=pa&&!ban[v]) res=min(res,dfs1(v,u)),siz[u]+=siz[v],mx=max(mx,siz[v]);
    return min(res,make_pair(max(mx,cursiz-siz[u]),u));
}
int dfs2(int u,int pa){
    int mx=0; siz[u]=1; for(int v:to[u]) if(v!=pa&&!ban[v]) mx=max(mx,dfs2(v,u)+1),siz[u]+=siz[v];
    return mx;
}
int dfs3(int u,int pa,int d){
    int mx=d; tmp[d]++; for(int v:to[u]) if(v!=pa&&!ban[v]) mx=max(mx,dfs3(v,u,d+1));
    return mx;
}
void dfs4(int u,int pa){
    dep[u]=1; son[u]=0; for(int v:to[u]) if(v!=pa&&!ban[v]) { dfs4(v,u); if(ckmax(dep[u],dep[v]+1)) son[u]=v; }
}
void dfs5(int u,int pa,int d){
    if(son[u]){
        f[son[u]]=f[u]+1; dfs5(son[u],u,d+1);
        ans+=2ll*siz[son[u]]*s1[0];
    }
    f[u][0]=1; int ss=siz[son[u]];
    for(int v:to[u]) if(v!=pa&&!ban[v]&&v!=son[u]){
        f[v]=ptr; ptr+=dep[v]; dfs5(v,u,d+1);
        int tt=ss; For(i,1,dep[v]) { ans+=2ll*f[v][i-1]*tt*(s1[0]-s1[max(0,i-d)]); tt-=f[u][i]; ans+=2ll*f[v][i-1]*tt*s1[max(0,i-d+1)]; }
        tt=0; Rev(i,dep[v]-1,0) { tt+=f[v][i]; ans+=2ll*f[u][i]*tt*(s1[0]-s1[max(0,i-d)]); ans+=2ll*f[u][i]*tt*s1[max(0,i-d+1)]; }
        ss+=siz[v]; For(i,1,dep[v]) f[u][i]+=f[v][i-1];
    }
}
void solve(int A){
    A=dfs1(A,0).second; D=dfs2(A,0);
    debug(A,D);
    For(i,0,D) c1[i]=c2[i]=s1[i]=s2[i]=0;
    c1[0]=1;
    for(int u:to[A]) if(!ban[u]){
        For(i,0,D) tmp[i]=0;; int d=dfs3(u,A,1);
        int tt=0; Rev(i,d,1) { c1[i]+=tmp[i]; c2[i]+=2ll*tt*tmp[i]+1ll*tmp[i]*(tmp[i]-1); tt+=tmp[i]; }
    }
    s1[D+1]=s2[D+1]=0; Rev(i,D,0) s1[i]=s1[i+1]+c1[i],s2[i]=s2[i+1]+c2[i];
    ans+=1ll*s1[1]*(s1[1]-1)-s2[1];
    for(int u:to[A]) if(!ban[u]){
        For(i,0,D) tmp[i]=0;; int d=dfs3(u,A,1);
        int tt=0; Rev(i,d,1) { c1[i]-=tmp[i]; c2[i]-=2ll*tt*tmp[i]+1ll*tmp[i]*(tmp[i]-1); tt+=tmp[i]; }
        Rev(i,d,0) s1[i]=s1[i+1]+c1[i],s2[i]=s2[i+1]+c2[i];
        For(i,1,d) ans+=tmp[i]*(1ll*s1[i+1]*(s1[i+1]-1)-s2[i+1]);
        dfs4(u,A); ptr=pool; f[u]=ptr; ptr+=dep[u]; dfs5(u,A,1);
            tt=0; Rev(i,d,1) { c1[i]+=tmp[i]; c2[i]+=2ll*tt*tmp[i]+1ll*tmp[i]*(tmp[i]-1); tt+=tmp[i]; }
        Rev(i,d,0) s1[i]=s1[i+1]+c1[i],s2[i]=s2[i+1]+c2[i];
    }
    debug(A,ans);
    ban[A]=1; for(int u:to[A]) if(!ban[u]) cursiz=siz[u],solve(u);
}
void solve(){
    cin>>n; ans=0; For(i,1,n) to[i].clear(),ban[i]=0;
    For(i,1,n-1) { int x,y; cin>>x>>y; to[x].push_back(y); to[y].push_back(x); }
    cursiz=n; solve(1); debug(ans); cout<<1ll*n*(n-1)*(n-2)-ans<<'\n';
}
signed main(){
    atexit([](){cerr<<"Time = "<<clock()<<" ms"<<endl;}); //ios::sync_with_stdio(0); cin.tie(0);
    int T; cin>>T; while(T--) solve();
    return 0;
}

// START TYPING IF YOU DON'T KNOW WHAT TO DO
// STOP TYPING IF YOU DON'T KNOW WHAT YOU'RE DOING
// CONTINUE, NON-STOPPING, FOR CHARLIEVINNIE

// Started Coding On: December 24 Sun, 20 : 39 : 04