#include <bits/stdc++.h>

 #define MOD 998244353

 #define ad(x,y,z) t[x][y]++,t[x][z+1]--

 using namespace std;

 long long T,n,LOG;

 char ch;

 long long a[],t[][],mi[];

 long long Mi[],ha[][];

 int main()

 {

     for(scanf("%d",&T);T;T--)

     {

         for(ch=getchar();!isalpha(ch);ch=getchar());

         for(n=;isalpha(ch);ch=getchar())

             a[++n]=ch-'a';

         LOG=;

         for(int i=;i<=n;i<<=,++LOG) mi[LOG]=i;

         Mi[]=;

         for(int i=;i<=n;i++)

             Mi[i]=Mi[i-]*%MOD;

         for(int i=;i<=n;i++)

             ha[i][]=a[i];

         for(int i=;i<=LOG;i++)

             for(int j=;j<=n-mi[i]+;j++)

                 ha[j][i]=ha[j][i-]*Mi[mi[i-]]%MOD+ha[j+mi[i-]][i-];

         for(int i=;i<=n;i++)

             t[][i]=,

             t[][i]=;

         for(int len=;len<=n/;len++)

         {

             for(int Now=,Nex=+len;Nex<=n;Now=Nex,Nex=Now+len)

             {

                 int now=Now,nex=Nex;

                 for(int i=LOG;i>=;i--)

                 if(nex+mi[i]-<=n)

                     if(ha[now][i]==ha[nex][i])

                         now+=mi[i],nex+=mi[i];

                 int lcp=min(now-Now,len);

                 now=Now,nex=Nex;

                 for(int i=LOG;i>=;i--)

                 if(now>=mi[i])

                     if(ha[now-mi[i]+][i]==ha[nex-mi[i]+][i])

                         now-=mi[i],nex-=mi[i];

                 int lcs=min(Now-now,len);

                 now=Now,nex=Nex;

                 if(lcp+lcs>=len)

                 {

                     ad(,nex-lcs+len,nex+lcp-);

                     ad(,now-lcs+,now+lcp-len);

                 }

             }

         }

         for(int i=;i<=n;i++)

             t[][i]+=t[][i-],

             t[][i]+=t[][i-];

         long long ans=;

         for(int i=;i<n;i++)

             ans+=t[][i]*t[][i+];

         printf("%lld\n",ans);

     }

     return ;

 }