#include <algorithm>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <vector>
typedef long long llt;
typedef unsigned uint;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T=uint,typename len_def=uint>
class Min_ST
{
    public:
        voi bzr(std::vector<T>V)
        {
            ST.clear();len_def k=V.size();
            for(len_def i=0;i<k;i++)ST.push_back(std::vector<T>()),ST[i].push_back(V[i]);
            for(len_def f=2;f<=k;f<<=1)for(len_def i=0;i+f<=k;i++)
                ST[i].push_back(std::min(ST[i].back(),ST[i+f/2].back()));
        }
        T Find(len_def Lnum,len_def Rnum)//log2不能打成log啊QAQ
        {
            len_def k=log2(Rnum-Lnum);return std::min(ST[Lnum][k],ST[Rnum-((len_def)1<<k)][k]);
        }
    private:
        std::vector<std::vector<T> >ST;
};
template<typename T=chr,typename len_def=uint>
class SA
{
	public:
		voi bzr(T*User,len_def n)
		{
			S.clear(),rk.clear(),sa.clear(),h.clear(),lcp_ready();
			for(len_def i=0;i<n;i++)S.push_back(User[i]),rk.push_back(0),sa.push_back(0),h.push_back(0);
			//倍增法求sa
			len_def done=1;
			while(done<2*n)
			{
				if(done!=1)
				{
					typedef std::pair<len_def,len_def>P;
					typedef std::pair<P,len_def>P2;
					std::vector<P2>q,tmp;std::vector<len_def>cnt;
					for(len_def i=0;i<n;i++)q.push_back(P2(P(rk[i]+1,(i+done/2<n)?rk[i+done/2]+1:0),i)),tmp.push_back(P2());
					for(len_def i=0;i<=n;i++)cnt.push_back(0);
					for(len_def i=0;i<n;i++)cnt[q[i].first.second]++;
			    	for(len_def i=1;i<=n;i++)cnt[i]+=cnt[i-1];
			    	for(len_def i=0;i<n;i++)tmp[--cnt[q[i].first.second]]=q[i];
					cnt.clear();for(len_def i=0;i<=n;i++)cnt.push_back(0);
			    	for(len_def i=0;i<n;i++)cnt[tmp[i].first.first]++;
			    	for(len_def i=1;i<=n;i++)cnt[i]+=cnt[i-1];
			    	for(len_def i=n-1;i+1;i--)q[--cnt[tmp[i].first.first]]=tmp[i];
			    	for(len_def i=0;i<n;i++)rk[q[i].second]=(i&&q[i].first==q[i-1].first)?rk[q[i-1].second]:i;
				}
				else
				{
					typedef std::pair<T,len_def>P;
					std::vector<P>q;
					for(len_def i=0;i<n;i++)q.push_back(P(User[i],i));
					std::sort(q.begin(),q.end());
			    	for(len_def i=0;i<n;i++)rk[q[i].second]=(i&&q[i].first==q[i-1].first)?rk[q[i-1].second]:i;
				}
				done<<=1;
			}
			for(len_def i=0;i<n;i++)sa[rk[i]]=i;
			len_def k=0;
			for(len_def i=0;i<n;i++)
			{
				if(k)k--;
				if(rk[i])
				{
					len_def j=sa[rk[i]-1];
					while(i+k<n&&j+k<n&&User[i+k]==User[j+k])k++;
					h[rk[i]]=k;
				}
			}
		}
		inline len_def rank(len_def num){return rk[num];}
		inline len_def s_a(len_def num){return sa[num];}
		inline len_def height(len_def num){return h[num];}
		inline voi lcp_ready(){p.bzr(h);}
		len_def lcp(len_def a,len_def b)
		{
			if(rk[a]>rk[b])std::swap(a,b);
			return(a==b)?S.size()-a:p.Find(rk[a]+1,rk[b]+1);
		}
	private:
		std::vector<T>S;std::vector<len_def>rk,sa,h;
		Min_ST<len_def,len_def>p;
};
SA<>s1,s2;
chr C1[30005],C2[30005];
uint L[30005]={0},R[30005]={0};
int main()
{
	uint t,n;ullt ans;scanf("%u",&t);
	while(t--)
	{
		scanf("%s",C1),s1.bzr(C1,n=strlen(C1)),s1.lcp_ready(),ans=0;
		for(uint i=0;i<n;i++)C2[i]=C1[n-i-1],L[i]=R[i]=0;s2.bzr(C2,n),s2.lcp_ready();
		for(uint k=1;(k<<1)<=n;k++)
		{
			uint p,q=k-1,l,r;
			while(q+k<n)
			{
				p=q,q+=k;
				if(C1[p]==C1[q])
				{
					r=std::min(s1.lcp(p,q),k),l=std::min(s2.lcp(n-p-1,n-q-1),k);
					for(uint i=p-l+1;i+k<=p+r;i++)R[i]++;
					for(uint i=q+r-1;i+l>=q+k;i--)L[i]++;
				}
			}
		}
		for(uint i=1;i+1<n;i++)ans+=(ullt)L[i]*R[i+1];
		printf("%llu\n",ans);
	}
	return 0;
}