#include <bits/stdc++.h>
#define M1(x) x=x-x/19260817*19260817
#define M2(x) x=x-x/2003110537*2003110537
using namespace std;


long long h1[5005], p1[5005];
long long h2[5005], p2[5005];
long long sml[5005];


char s[5005];
int n;
bool eq(int l, int r, int z, int y){
    long long x1 = h1[r] - h1[l-1] * p1[r-l+1];
    long long y1 = h1[y] - h1[z-1] * p1[y-z+1];
    long long x2 = h2[r] - h2[l-1] * p2[r-l+1];
    long long y2 = h2[y] - h2[z-1] * p2[y-z+1];
    M1(x1);
    M1(y1);
    M2(x2);
    M2(y2);
    if(x1 < 0) x1 += 19260817;
    if(y1 < 0) y1 += 19260817;
    if(x2 < 0) x2 += 2003110537;
    if(y2 < 0) y2 += 2003110537;
    if(x1 == y1 && x2 == y2){
        return true;
    }
    else return false;
}

struct HashFunc
{
    template<typename T, typename U>
    size_t operator()(const std::pair<T, U>& p) const {
    return std::hash<T>()(p.first) ^ std::hash<U>()(p.second);
    }
};

struct EqualKey {
    template<typename T, typename U>
    bool operator ()(const std::pair<T, U>& p1, const std::pair<T, U>& p2) const {
    return p1.first == p2.first && p1.second == p2.second;
    }
};


unordered_map<pair<int,int>, int, HashFunc, EqualKey> sum;
pair<int,int> cal(int l, int r){
    long long x1 = h1[r] - h1[l-1] * p1[r-l+1];
    long long x2 = h2[r] - h2[l-1] * p2[r-l+1];
    M1(x1);
    M2(x2);
    if(x1 < 0) x1 += 19260817;
    if(x2 < 0) x2 += 2003110537;
    return {(int)x1, (int)x2};
}

int main()
{
    int T;
    T = 1;
    scanf("%d", &T);
    p1[0] = p2[0] = 1;
    for(int i = 1; i <= 5000; i++){
        p1[i] = p1[i-1] * 233;
        M1(p1[i]);
        p2[i] = p2[i-1] * 157;
        M2(p2[i]);
    }
    while(T--){
        //for(int i = 1; i <= 5000; i++)
        //    s[i] = '0';
        scanf("%s", s+1);
        n = strlen(s+1);
        //cout<<n<<endl;

        long long ans = 0;
        for(int i = 1; i <= n; i++){
            h1[i] = h1[i-1] * 233 + s[i];
            M1(h1[i]);
            h2[i] = h2[i-1] * 157 + s[i];
            M2(h2[i]);
        }
        for(int len = 1; len <= n; len++){
            for(int l = n-2*len; l >= 1; l--){
                pair<int,int> lst = cal(l+1+len, l+len*2);
                sum[lst]++;
                pair<int,int> nw = cal(l, l+len-1);
                ans += sum[nw] * sml[l];
                if(eq(l, l+len-1, l+len, l+2*len-1)){
                    sml[l+len]++;
                }
            }
            sum.clear();
        }
        printf("%lld\n", ans);
        ans = 0;
        sum.clear();
        for(int i = 0; i <= n; i++)
            sml[i] = 0;
    }
    return 0;
}