import d.time: clock;
import d.xio: xfile;
import std.string: stripr, toString;

int count(string s) {
    int result;
    int n = s.length;
    s ~= " ";
    auto a = new int[][](128, 0);

    for (int i = n - 1; i > -1; i--) {
        int lev;
        for (int st = a[s[i]].length - 1; st > -1; st--) {
            int j = a[s[i]][st];
            if (n - j <= lev)
                break;
            if (s[j + lev] != s[i + lev])
                continue;
            if (s[j + lev / 2] != s[i + lev / 2])
                continue;
            int k;
            while (s[j + k] == s[i + k])
                k++;
            if (k > lev)
                lev = k;
        }
        a[s[i]] ~= i;
        result += n - i - lev;
    }
    return result;
}

void main() {
    auto t0 = clock();
    auto fin = xfile("input.txt");
    auto fout = xfile("output.txt", "w");
    fin.readline();
    foreach (line; fin)
        fout.write(toString(count(line.stripr())) ~ \n);
    fout.write(toString(clock() - t0) ~ \n);
    fout.close();
}