#include<bits/stdc++.h>
using namespace std;
#define ll long long

const int N = 3e5+10;
string s;

struct PaliTree{
    #define sz 26
    struct node{
        int lng;
        int link;
        int next[sz];
        ll oc;
        node(int _lng){
            lng = _lng;
            link = 0;
            oc = 0;
            memset(next,-1,sizeof(next));
        }
    };

    vector<node> tree;
    int cur;
    
    PaliTree(){
        tree.push_back(node(-1)); //img
        tree.push_back(node(0)); //root
        cur = 1;
    }

    int get_id(char c){return c-'a';}

    int get_link(int now,int i){
        char c = s[i];
        while(1){
            if(now == 0 or (i-1-tree[now].lng > 0 and s[i-1-tree[now].lng] == c)) break;
            now = tree[now].link;
        }
        int id = get_id(c);
        return (tree[now].next[id] == -1)?now:tree[now].next[id];
    }

    void add(int i){
        char c = s[i];
        int id = get_id(c);
        while(1){
            if(cur == 0 or (i-1-tree[cur].lng > 0 and s[i-1-tree[cur].lng] == c)) break;
            cur = tree[cur].link;
        }
        if(cur == 0 and s[i] == s[i-1]) cur = 1;
        if(tree[cur].next[id] == -1){
            node tmp(tree[cur].lng+2);
            if(tmp.lng == 1) tmp.link = 1;
            else tmp.link = get_link(tree[cur].link,i);
            tree.push_back(tmp);
            tree[cur].next[id] = tree.size()-1;
        }
        // cerr << i << ' ' << cur << ' ';
        cur = tree[cur].next[id];
        // cerr << cur << '\n';
        tree[cur].oc++;
    }

    void calc(){
        for(int i = tree.size() - 1; i > 1; i--){
            tree[tree[i].link].oc += tree[i].oc;
        }
    }

    void clear() {
        tree.clear();
        tree.push_back(node(-1)); //img
        tree.push_back(node(0)); //root
        cur = 1;
    }
}pt;

ll sum[N],ans;

void dfs(int u) {
    if(u != 1) sum[u] = pt.tree[u].oc;
    for(int i = 0; i < 26; i++) {
        int nu = pt.tree[u].next[i];
        if(nu != -1) {
            dfs(nu);
            sum[u] += sum[nu];
        }
    }
}

void dfs2(int u) {
    for(int i = 0; i < 26; i++) {
        int nu = pt.tree[u].next[i];
        if(nu != -1) {
            ans += sum[nu] * (sum[1] - sum[nu]);
            dfs2(nu);
        }
    }
}

void solve() {
    cin >> s;
    s = "#" + s;
    for(int i = 1; i < s.size(); i++) {
        pt.add(i);
    }
    pt.calc();
    for(int i = 1; i < pt.tree.size(); i++) {
        sum[i] = 0;
    }
    dfs(1);
    ans = 0;
    dfs2(1);
    cout << ans << '\n';
    pt.clear();
    return;
}

int32_t main() {
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    int tc = 1;
    cin >> tc;
    for(int kase = 1; kase <= tc; kase++) {
        //cout << "Case " << kase << ": ";
        solve();
    }
    return 0;
}