//-DYUNQIAN -std=c++14 -O2 -Wall
#include<bits/stdc++.h>

#define ll long long
#define fi first
#define se second
#define mk make_pair

using namespace std;

inline int read(){
    int x=0,f=1;char c=getchar();
    for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
    for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
    return x*f;
}

const int mod=1e9+7;
int ksm(int x,int y,int p=mod){
    int ans=1;
    for(int i=y;i;i>>=1,x=1ll*x*x%p)if(i&1)ans=1ll*ans*x%p;
    return ans%p;
}
int inv(int x,int p=mod){return ksm(x,p-2,p)%p;}
mt19937 rnd(time(0));
int randint(int l,int r){return rnd()%(r-l+1)+l;}
void add(int &x,int v){x+=v;if(x>=mod)x-=mod;}
void Mod(int &x){if(x>=mod)x-=mod;}

void Assert(bool c,int L=0){if(!c){cout<<"Assertion Failed at "<<L<<endl;exit(0);}}

void cmax(int &x,int v){x=max(x,v);}
void cmin(int &x,int v){x=min(x,v);}

const int N=5005;

vector<int>G[N<<1];
int n,m,f[N][N];
namespace sam{
	const int D=10;
	int nxt[N<<1][D],len[N<<1],lst=1,tot=1;
	int pos[N<<1],st[N<<1],ed[N<<1],fa[N<<1];
	void ins(int c){
//		cout<<"ins "<<c<<endl;
		int np=++tot,p=lst;len[np]=len[p]+1,lst=np,pos[np]=len[np];
//		cout<<"p = "<<p<<endl;
		while(p&&nxt[p][c]==0)nxt[p][c]=np,p=fa[p];
		if(p==0){fa[np]=1;return ;}
		int q=nxt[p][c];
		if(len[q]==len[p]+1){fa[np]=q;return ;}
		int nq=++tot;len[nq]=len[p]+1;
		fa[nq]=fa[q],fa[q]=fa[np]=nq,memcpy(nxt[nq],nxt[q],sizeof(nxt[nq]));
		while(p&&nxt[p][c]==q)nxt[p][c]=nq,p=fa[p];
	}
	set<int>endp[N<<1];
	void buildTree(){
//		V=tot;
		for(int i=1;i<=tot;i++){
			if(fa[i])G[fa[i]].emplace_back(i);
			st[i]=len[fa[i]]+1,ed[i]=len[i];
			if(pos[i])endp[i].insert(pos[i]);
		}
	}
	void Merge(set<int>&A,set<int>&B){
		if(A.size()<B.size())swap(A,B);
		for(int x:B)A.insert(x);B.clear();
	}
	void getans(){
//		cout<<"tot = "<<tot<<endl;
		buildTree();
		function<void(int)>dfs=[&](int u){
//			cout<<"dfs "<<u<<endl;
			for(int v:G[u])dfs(v);
			for(int v:G[u])Merge(endp[u],endp[v]);
			vector<int>P;
//			cout<<"calc "<<u<<" endpos = ";for(int x:endp[u])cout<<x<<" ";puts("");
//			cout<<"st,ed = "<<st[u]<<","<<ed[u]<<endl;
			for(int x:endp[u])P.emplace_back(x);
			for(int L=st[u];L<=ed[u];L++){
				int p=P.size();
				for(int i=(int)P.size()-1;i>=0;i--){
					int r=P[i],l=P[i]-L+1;
					while(p>0&&P[p-1]-L+1>r+1)p--;
					f[l][r]=P.size()-p;
//					cout<<"f ["<<l<<","<<r<<"] = "<<f[l][r]<<endl;
				}
			}
		};
		dfs(1);
	}
	void clear(){
		for(int i=1;i<=tot;i++)memset(nxt[i],0,sizeof(nxt[i])),len[i]=pos[i]=st[i]=ed[i]=fa[i]=0,endp[i].clear(),G[i].clear();
		lst=1,tot=1;
	}
};

string str;
int lcp[N][N];
void solve(){
	cin>>str;n=str.size();sam::clear();
	for(int i=1;i<=n;i++)sam::ins(str[i-1]-'0');
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)lcp[i][j]=(str[i-1]==str[j-1]?lcp[i+1][j+1]+1:0);
	sam::getans();
	
	for(int i=1;i<=n;i++)for(int j=n-1;j>=i;j--)f[i][j]+=f[i][j+1];
	ll ans=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<i;j++){
			if(lcp[i][j]>=i-j)ans+=f[i][2*i-j];
		}
	}
	cout<<ans<<endl;
	
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)f[i][j]=lcp[i][j]=0;
}

signed main(void){

#ifdef YUNQIAN
    freopen("B.in","r",stdin);
#endif

	int tt=read();while(tt--)solve();

    return 0;
}