//                              -    주의 만세!

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<tuple>
#include<string>

#define fi first
#define se second
#define mkp std::make_pair
using ll=long long;
using llu=unsigned long long;
using std::max;
using std::min;
template<class T> void cmax(T&a,T b){a=max(a,b);}
template<class T> void cmin(T&a,T b){a=min(a,b);}
template<class T> T sqr(T a){return a*a;}

const int NV=1e6;

const int B=1145141;
std::string str[NV+5];
std::vector<llu> hsh[NV+5];
llu pw[NV+5];
llu hs(int x,int l,int r){
    return hsh[x][r]-(!l?0:hsh[x][l-1]*pw[r-l+1]);
}int cmp(int a,int b,int c,int d){
    int len=min(str[a].size()-b,str[c].size()-d),l=0,r=len+1;
    while(l+1<r){
        int mid=l+r>>1;
        if(hs(a,b,b+mid-1)==hs(c,d,d+mid-1))
            l=mid;
        else r=mid;
    }
    int stat=-int(b+l==(int)str[a].size())+int(d+l==(int)str[c].size());
    if(b+l==(int)str[a].size()||d+l==(int)str[c].size()) return stat;
    return (int)str[a][b+l]-(int)str[c][d+l];
}int calc(int x,int y){
    int l=0,r=y;
    while(l+1<r){
        int mid=l+r>>1;
        if(cmp(mid,0,y,str[x].size())>0)
            r=mid;
        else l=mid;
    }
    return r;
}

namespace bit{
    int tr[NV+5],n;
    void add(int x,int z){
        for(;x<=n;x+=x&-x) tr[x]+=z;
    }int que(int x){
        int ans=0;
        for(;x;x-=x&-x) ans+=tr[x];
        return ans;
    }
}

namespace trie{
    std::vector<int> e[NV+5];
    int g[NV+5][26],cnt=1;
    void ins(const char*sz,int wtf){
        int p=1;
        for(int i=0;sz[i];++i){
            int c=sz[i]-'a';
            if(!g[p][c]) g[p][c]=++cnt;
            p=g[p][c];
        }
        e[p].push_back(wtf);
    }
    ll ans=0;
    int wtf[NV+5][2];
    std::vector<std::pair<int,int> > stk;
    void dfs(int x){
        if(e[x].size()){
            ans+=(ll)e[x].size()*(e[x].size()-1)*(e[x].size()-2)/6;
            ans+=(ll)e[x].size()*(e[x].size()-1)/2*(e[x][0]-1);
            for(auto p:stk){
                int w=calc(p.fi,e[x][0]);
                ans+=ll(e[x][0]-w)*e[x].size()*p.se;
            }
            std::vector<std::tuple<int,int,int,int> > eve;
            for(auto p:stk){
                eve.emplace_back(p.fi,0,p.fi,0);
                eve.emplace_back(e[x][0],str[p.fi].size(),p.fi,1);
            }
            std::sort(eve.begin(),eve.end(),[&](
                        std::tuple<int,int,int,int> u,
                        std::tuple<int,int,int,int> v){
                    return cmp(std::get<0>(v),std::get<1>(v),
                            std::get<0>(u),std::get<1>(u))>0;});
            int now=0;
            std::tuple<int,int,int,int> lst={-1,-1,-1,-1};
            for(auto z:eve){
                if(std::get<0>(lst)==-1||cmp(std::get<0>(z),std::get<1>(z),
                            std::get<0>(lst),std::get<1>(lst)))
                    ++now;
                wtf[std::get<2>(z)][std::get<3>(z)]=now;
                lst=z;
            }
            bit::n=now;
            std::vector<std::tuple<int,int,int> > vq;
            ll s1=0,s2=0;
            for(auto p:stk){
                vq.emplace_back(wtf[p.fi][1]+1,-wtf[p.fi][0],p.se);
                vq.emplace_back(wtf[p.fi][0],wtf[p.fi][1],p.se);
                if(wtf[p.fi][0]>wtf[p.fi][1]){
                    ans+=(ll)e[x].size()*p.se*(p.se-1)/2;
                    s1+=(ll)e[x].size()*p.se*p.se;
                }
            }
            std::sort(vq.begin(),vq.end());
            for(auto p:vq){
                int u,f;
                std::tie(std::ignore,u,f)=p;
                if(u<0) bit::add(-u,f);
                else s2+=(ll)e[x].size()*(bit::que(bit::n)-bit::que(u))*f;
            }
            ans-=s1+(s2-s1)/2;
            for(auto p:vq){
                int u,f;
                std::tie(std::ignore,u,f)=p;
                if(u<0) bit::add(-u,-f);
            }
        }
        if(e[x].size()) stk.emplace_back(e[x][0],e[x].size());
        for(int i=0;i<26;++i) if(g[x][i]) dfs(g[x][i]);
        if(e[x].size()) stk.pop_back();
    }
}

namespace xm{
    char tsz[NV+5];
    void _(){
        int N;
        scanf("%d",&N);
        memset(trie::g+1,0,sizeof*trie::g*trie::cnt);
        for(int i=1;i<=trie::cnt;++i) trie::e[i].clear();
        trie::cnt=1;
        for(int i=1;i<=N;++i){
            scanf("%s",tsz);
            str[i]=tsz;
        }
        std::sort(str+1,str+N+1);
        for(int i=1;i<=N;++i){
            trie::ins(str[i].c_str(),i);
            llu cur=0;
            hsh[i].clear();
            for(auto c:str[i]){
                cur=cur*B+c;
                hsh[i].push_back(cur);
            }
        }
        trie::ans=0;
        trie::dfs(1);

        printf("%lld\n",trie::ans);
    }
}

int main(){
    int t;
    pw[0]=1;
    for(int i=1;i<NV+5;++i) pw[i]=pw[i-1]*B;
    scanf("%d",&t);
    while(t--) xm::_();
    return 0;
}