#include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define mem(a) memset(a,0,sizeof(a))

 #define LCP(x,y) SA.que(x,y)

 #define LCS(x,y) SA1.que(n-y+1,n-x+1)

 #define rep(i,l,r) for (int i=(l); i<=(r); i++)

 typedef long long ll;

 using namespace std;

 const int N=;

 int n,T,f[N],g[N],log[N];

 char s[N]; ll ans;

 struct Suffix{

     int lst,cnt,np,tot,h[N],pos[N],x[N],b[N],mx[N];

     int son[N][],fa[N],ch[N][],rk[N],sa[N],st[N][];

     void init(){ lst=cnt=; tot=; mem(b); mem(ch); mem(fa); mem(son); }

     void ext(int c,int k){

         int p=lst; lst=np=++cnt; pos[np]=k; b[np]=; mx[np]=mx[p]+;

         while (p && !son[p][c]) son[p][c]=np,p=fa[p];

         if (!p) fa[np]=;

         else{

             int q=son[p][c];

             if (mx[q]==mx[p]+) fa[np]=q;

             else{

                 int nq=++cnt; mx[nq]=mx[p]+; pos[nq]=pos[q];

                 while (p && son[p][c]==q) son[p][c]=nq,p=fa[p];

                 memcpy(son[nq],son[q],sizeof(son[nq]));

                 fa[nq]=fa[q]; fa[q]=fa[np]=nq;

             }

         }

     }

     void build(){ rep(i,,cnt) ch[fa[i]][x[pos[i]+mx[fa[i]]]]=i; }

     void dfs(int x){

         if (b[x]) sa[rk[pos[x]]=++tot]=pos[x];

         rep(i,,) if (ch[x][i]) dfs(ch[x][i]);

     }

     void get(){

         int k=;

         rep(i,,n){

             for (int j=sa[rk[i]-]; i+k<=n && j+k<=n && x[i+k]==x[j+k]; k++);

             h[rk[i]]=k; if (k) k--;

         }

     }

     void rmq(){

         rep(i,,n) st[i][]=h[i];

         rep(i,,log[n])

         rep(j,,n-(<<i)+) st[j][i]=min(st[j][i-],st[j+(<<(i-))][i-]);

     }

     int ask(int l,int r){

         l++; int t=log[r-l+];

         return min(st[l][t],st[r-(<<t)+][t]);

     }

     int que(int x,int y){ return ask(min(rk[x],rk[y]),max(rk[x],rk[y]));}

     void build_sa(char s[]){

         for (int i=n; i; i--) ext(x[i]=s[i]-'a'+,i);

         build(); dfs(); get(); rmq();

     }

 }SA,SA1;

 void solve(){

     mem(f); mem(g);

     for (int len=,x,y,l,r; *len<=n; len++)

         for (int i=,j=len+; j<=n; i+=len,j+=len)

             if (s[i]==s[j]){

                 x=LCS(i,j); y=LCP(i,j);

                 l=max(i,i-x+len); r=min(i+y,j);

                 if (r>l){

                     f[l+len]++; f[r+len]--;

                     g[l-len+]++; g[r-len+]--;

                 }

             }

     rep(i,,n) f[i]+=f[i-],g[i]+=g[i-];

     rep(i,,n-) ans+=(ll)f[i]*g[i+];

 }

 int main(){

     freopen("bzoj4650.in","r",stdin);

     freopen("bzoj4650.out","w",stdout);

     log[]=; rep(i,,N) log[i]=log[i>>]+;

     scanf("%d",&T);

     while (T--){

         SA.init(); SA1.init(); scanf("%s",s+); n=strlen(s+);

         SA.build_sa(s); reverse(s+,s+n+);

         SA1.build_sa(s); reverse(s+,s+n+);

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

     }

     return ;

 }