#define _CRT_SECURE_NO_DEPRECATE
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <memory>
#include <memory.h>
#include <set>
#include <vector>
#include <time.h>
#include <string>
#include <string.h>
#include <queue>
#include <stdlib.h>
using namespace std;
typedef long long li;
typedef long double ld;
typedef vector <int> vi;
typedef pair < int, int > pi;
#define pb push_back
#define mp make_pair
void solve ();
int main()
{
#ifdef _DEBUG
    freopen ("in.txt", "r", stdin);
    //freopen ("out.txt", "w", stdout);
#endif
    int t;
    scanf ("%d", &t);
    getchar();
    while (t--)
    solve();
}
//#define int li
const int maxlen=100500;
char s[maxlen];
int p[maxlen];
int n;
int c[maxlen];
int cnt[maxlen];
int pn[maxlen], cn[maxlen];
int lcp[maxlen], lcpn[maxlen], lpos[maxlen], rpos[maxlen];
int classes=1;
const int shift=1<<16;
int tree[2*shift+2];
void rmq_build ()
{
    memset (tree, 0, sizeof (tree));
    for ( int i=shift; i<shift+n; i++ )
        tree[i]=lcp[i-shift];
    for (int i=shift-1; i>0; i-- )
        tree[i]=min ( tree[2*i], tree[2*i+1] );
}
int rmq ( int l, int r )
{
    if (l>r)
        return 1<<30;
    if ( (l%2) )
        return min ( tree[l], rmq(l+1, r) );
    if ( !(r%2) )
        return min ( tree[r], rmq (l, r-1) );
    return rmq (l/2, r/2);
}
void solve ()
{
    gets (s);
    n=strlen(s)+1;
    memset (lcp, 0, sizeof (lcp));
    memset (cnt, 0, sizeof (cnt));
    for ( int i=0; i<n; i++ )
        cnt[s[i]]++;
    for (int i=1; i<=256; i++)
        cnt[i]+=cnt[i-1];
    for ( int i=0; i<n; i++ )
        p[--cnt[s[i]]]=i;
    c[p[0]]=0;
    for ( int i=1; i<n; i++ )
    {
        if ( s[p[i]]!=s[p[i-1]] )
            classes++;
        else
            lcp[i-1]=1;
        c[p[i]]=classes-1;
    }
    for ( int h=0; (1<<h)<n; h++ )
    {
        for (int i=0; i<n; ++i)
        rpos[c[p[i]]] = i;
        for (int i=n-1; i>=0; --i)
        lpos[c[p[i]]] = i;

        for ( int i=0; i<n; i++ )
        {
            pn[i]=p[i]-(1<<h);
            if (pn[i]<0)
                pn[i]+=n;
        }
        memset (cnt, 0, sizeof (cnt));
        for (int i=0; i<n; i++)
            cnt[c[pn[i]]]++;
        for (int i=1; i<classes; i++)
            cnt[i]+=cnt[i-1];
        for (int i=n-1; i>=0; i--)
            p[--cnt[c[pn[i]]]]=pn[i];
        cn[p[0]]=0;
        classes=1;
        for (int i=1; i<n; i++)
        {
            int m1=(p[i]+(1<<h))%n, m2=(p[i-1]+(1<<h))%n;
            if ( c[p[i]]!=c[p[i-1]] || c[m1]!=c[m2] )
                classes++;
            cn[p[i]]=classes-1;
        }

        rmq_build ();
        for (int i=0; i<n-1; ++i) {
        int a = p[i],  b = p[i+1];
        if (c[a] != c[b])
            lcpn[i] = lcp[rpos[c[a]]];
        else {
            int aa = (a + (1<<h)) % n,  bb = (b + (1<<h)) % n;
            lcpn[i] = (1<<h) + rmq (lpos[c[aa]]+shift, rpos[c[bb]]-1+shift);
            lcpn[i] = min (n, lcpn[i]);
        }
    }
    memcpy (lcp, lcpn, n * sizeof(int));
    memcpy (c, cn, n * sizeof(int));
    }
    li ans=0;
    for (int i=0; i<n-1; i++)
    {
        int len2=n-1-p[i+1]-lcp[i];
        ans+=(li)len2;
    }
    printf ("%lld\n", ans);
}