#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long u64;
struct LongestCommonPrefix {
  int n;
  vector<int> sa, rk;
  vector<vector<int>> st;
  LongestCommonPrefix(const string &s) : n(s.size()), sa(n), rk(n) {
    int k = 0;
    vector<int> q, count;
    for (int i = 0; i < n; i += 1) sa[i] = i;
    sort(sa.begin(), sa.end(), [&](int i, int j) { return s[i] < s[j]; });
    for (int i = 0; i < n; i += 1)
      rk[sa[i]] = i and s[sa[i]] == s[sa[i - 1]] ? rk[sa[i - 1]] : k++;
    for (int m = 1; m < n; m *= 2) {
      q.resize(m);
      for (int i = 0; i < m; i += 1) q[i] = n - m + i;
      for (int i : sa)
        if (i >= m) q.push_back(i - m);
      count.assign(k, 0);
      for (int i : rk) count[i] += 1;
      for (int i = 1; i < k; i += 1) count[i] += count[i - 1];
      for (int i = n - 1; i >= 0; i -= 1) sa[count[rk[q[i]]] -= 1] = q[i];
      auto cur = rk;
      cur.resize(2 * n, -1);
      k = 0;
      for (int i = 0; i < n; i += 1)
        rk[sa[i]] = i and cur[sa[i]] == cur[sa[i - 1]] and
                             cur[sa[i] + m] == cur[sa[i - 1] + m]
                         ? rk[sa[i - 1]]
                         : k++;
    }
    st.emplace_back(n);
    for (int i = 0, k = 0; i < n; i += 1) {
      if (not rk[i]) continue;
      k = max(k - 1, 0);
      int j = sa[rk[i] - 1];
      while (i + k < n and j + k < n and s[i + k] == s[j + k]) k += 1;
      st[0][rk[i]] = k;
    }
    for (int i = 1; (1 << i) < n; i += 1) {
      st.emplace_back(n - (1 << i) + 1);
      for (int j = 0; j <= n - (1 << i); j += 1)
        st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
    }
  }
  int get(int i, int j) {
    if (i == j) return n - i;
    if (i == n or j == n) return 0;
    i = rk[i];
    j = rk[j];
    if (i > j) swap(i, j);
    int k = 64 - __builtin_clzll(u64(j - i)) - 1;
    return min(st[k][i + 1], st[k][j - (1 << k) + 1]);
  }
};
/*
    input 0 base
    output [l,r,sa] 1base 
*/
pair<vector<tuple<int, int, int>>,LongestCommonPrefix> run(const string &s) {
  int n = s.size();
  auto r = s;
  reverse(r.begin(), r.end());
  LongestCommonPrefix lcp(s), lcs(r);
  vector<tuple<int, int, int>> runs;
  for (bool inv : {false, true}) {
    vector<int> lyn(n, n), stack;
    for (int i = 0; i < n; i += 1) {
      while (not stack.empty()) {
        int j = stack.back(), k = lcp.get(i, j);
        if (i + k < n and ((s[i + k] > s[j + k]) ^ inv)) break;
        lyn[j] = i;
        stack.pop_back();
      }
      stack.push_back(i);
    }
    for (int i = 0; i < n; i += 1) {
      int j = lyn[i], t = j - i, l = i - lcs.get(n - i, n - j),
          r = j + lcp.get(i, j);
      if (r - l >= 2 * t) runs.emplace_back(l,r-1,t);
    }
  }
  sort(runs.begin(), runs.end());
  runs.erase(unique(runs.begin(), runs.end()), runs.end());
  return make_pair(runs,lcp);
}
const int N=1e6+10;
const ll p1=31,p2=131;
const ll mod1=1e9+7,mod2=1e9+9;
typedef pair<ll,ll> hs;
const hs p = make_pair(p1,p2);
hs &operator+=(hs &a, hs b) {
    a.first=(a.first+b.first)%mod1;
    a.second=(a.second+b.second)%mod2;
    return a;
}
hs operator+(hs a, hs b) { return a += b; }
hs &operator-=(hs &a, hs b) {
    a.first=(a.first-b.first+mod1)%mod1;
    a.second=(a.second-b.second+mod2)%mod2;
    return a;
}
hs operator-(hs a, hs b) { return a -= b; }
hs &operator*=(hs &a, hs b) {
    a.first=(a.first*b.first)%mod1;
    a.second=(a.second*b.second)%mod2;
    return a;
}
hs operator*(hs a, hs b) { return a *= b; }
struct Hash{
    int n;
    vector<hs>has1,has2,Pow;
    void Hash_init(string &s){
        n=(int)s.size();
        Pow.resize(n+2);
        has1.resize(n+2);
        has2.resize(n+2);
        Pow[0]=make_pair(1ll,1ll);
        for(int i=1;i<=n;i++)Pow[i]=Pow[i-1]*p;
        for(int i=1;i<=n;i++)has1[i]=has1[i-1]*p+hs{s[i-1]-'a'+1,s[i-1]-'a'+1};
        for(int i=n;i>=1;i--)has2[i]=has2[i+1]*p+hs{s[i-1]-'a'+1,s[i-1]-'a'+1};
    }
    hs get1(int l,int r){
        return has1[r]-has1[l-1]*Pow[r-l+1];
    }
    hs get2(int l,int r){
        return has2[l]-has2[r+1]*Pow[r-l+1];
    }
};
ll solve()
{
    string s;cin>>s;
    auto [runs,lcp]=run(s);
    ll ans=0;
    int n=s.size();
    Hash has;has.Hash_init(s);
    for(int i=0;i<n;i++)ans+=n-(i+lcp.st[0][lcp.rk[i]]);
    unordered_map<ll,int> ma;
    auto insert =[&](hs x){
        ma[x.first*(mod2+3)+x.second]=1;
    };
    for(auto [l,r,p]:runs){
        for(int x=l;x<l+p;x++){
            for(int y=x+p-1;y+p<=r;y+=p)insert(has.get1(x+1,y+1));
        }
    }
    return ans-(ll)ma.size();
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;cin>>T;while(T--)cout<<solve()<<"\n";
    return 0;
}