#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define pb push_back
#define ff first
#define sc second

vector<int> manacher(string s) {
    int n = (int) s.size();
    vector<int> d(n, 1);
    int l = 0, r = 0;
    for (int i = 1; i < n; i++) {
        if (i < r)
            d[i] = min(r - i + 1, d[l + r - i]);
        while (i - d[i] >= 0 && i + d[i] < n && s[i - d[i]] == s[i + d[i]])
            d[i]++;
        if (i + d[i] - 1 > r)
            l = i - d[i] + 1, r = i + d[i] - 1;
    }
    return d;
}

vector<int> manacher2(string s) {
    vector<int> ans(s.size());
    int l = -1, r = -1;
    for (int i = 0; i < s.size(); i++) {
        if (i > r) {
            l = i; r = i;
            while (l - 1 >= 0 && r + 1 < s.size() && s[l - 1] == s[r + 1]) { r++; l--; }
            ans[i] = r - l + 1;
        } else {
            int cl = ans[l + r - i];
            if (cl / 2 + i < r) {
                ans[i] = cl;
            } else {
                ans[i] = 1 + (r - i) * 2;
                while (r + 1 < s.size() && 2 * i - (r + 1) >= 0 && s[r + 1] == s[2 * i - (r + 1)]) {
                    ans[i] += 2;
                    r++;
                    l = 2 * i - r;
                }
            }
        }
    }
    return ans;
}

const ll mod1 = 1e9 + 7, mod2 = 998244353;
const ll p = 31;

struct polyhash {
    int n;
    vector<int> c;
    vector<pair<ll, ll>> h, ppow;
    polyhash() = default;
    polyhash(int n_, vector<int> c_) {
        n = n_;
        c = c_;
        h.assign(n + 1, {0, 0});
        ppow.assign(n + 1, {1, 1});
        for (int i = 1; i <= n; i++) {
            h[i] = {(h[i - 1].first * p + c[i - 1]) % mod1, 
                    (h[i - 1].second * p + c[i - 1]) % mod2};
            ppow[i] = {(ppow[i - 1].first * p) % mod1, 
                       (ppow[i - 1].second * p) % mod2};
        }
    }

    pair<ll, ll> substring(int l, int r) {
        // [l, r] is segment in 0-index
        pair<ll, ll> result = {(h[r + 1].first + mod1 - (h[l].first * ppow[r - l + 1].first) % mod1), 
                (h[r + 1].second + mod2 - (h[l].second * ppow[r - l + 1].second) % mod2)};
        if (result.first >= mod1) result.first -= mod1;
        if (result.second >= mod2) result.second -= mod2;
        return result;
    }

    int find_lcp(int p1, int p2) {
        // finds longest common prefix of suffixes starts with indexes p1 and p2
        // useful for suffix array
        int L = 0, R = min(n - p1, n - p2) + 1;
        while (R - L > 1) {
            int M = (L + R) / 2;
            if (substring(p1, p1 + M - 1) == substring(p2, p2 + M - 1)) L = M;
            else R = M;
        }
        return L;
    }
};

struct sufarr {
    int n;
    vector<int> a;
    vector<int> cl;
    sufarr() = default;
    sufarr(int n_, vector<int> a_) {
        n = n_;
        a = a_;
        build();
    }
  
    void build() {
        vector<int> ord(n);
        iota(all(ord), 0);
        sort(all(ord), [&](int i, int j){return a[i] < a[j];});
  
        vector<pair<int, int>> lol(n);
        cl.assign(n, 0);
        int cur = -1;
        for (int i = 0; i < n; i++) {
            if (i == 0 || a[ord[i]] != a[ord[i - 1]]) cur++;
            cl[ord[i]] = cur;
        }
        for (int len = 2; len < 2 * n; len *= 2) {
            int l2 = len / 2;
            for (int i = 0; i < n; i++) {
                lol[i] = {cl[i], (i + l2 < n ? cl[i + l2] : -1)};
            }
            sort(all(ord), [&](int i, int j) {return lol[i] < lol[j];});
            int cur = -1;
            for (int j = 0; j < n; j++) {
                if (j == 0 || lol[ord[j]] != lol[ord[j - 1]]) cur++;
                cl[ord[j]] = cur;
            }
        }
    }
};

struct dsu {
    int n, bs = 0;
    vector<int> par, siz, sm;
    dsu() = default;
    dsu(int n_) {
        n = n_;
        bs = 0;
        par.assign(n, 0);
        siz.assign(n, 1);
        sm.assign(n, 0);
        iota(all(par), 0);
    }
    int get(int v) {return (par[v] == v ? v : par[v] = get(par[v]));}
    int getsum(int v) {return sm[get(v)];}
    void upd_sum(int v, int val) {sm[get(v)] += val; bs = max(bs, sm[get(v)]);}
    bool merge(int u, int v) {
        u = get(u); v = get(v); if (u == v) return false;
        if (siz[u] < siz[v]) swap(u, v);
        par[v] = u;
        siz[u] += siz[v];
        sm[u] += sm[v];
        bs = max(bs, sm[u]);
        return true;
    }
};

void solve() {
    string s; cin >> s;
    int n = s.size();
    vector<int> arr(s.size());
    for (int i = 0; i < n; i++) arr[i] = (s[i] - 'a' + 1);
    string nww = ".";
    for (int i = 0; i < s.size(); i++) {
        nww += s[i];
        nww += '.';
    }
    auto result = manacher(nww);
    for (int& x : result) x = 2 * x - 1;

    sufarr sf(n, arr);
    vector<int> order(n), pos = sf.cl;
    for (int i = 0; i < n; i++) order[sf.cl[i]] = i;
    polyhash pl(n, arr);
    vector<int> lcp(n - 1);
    for (int i = 0; i < n - 1; i++) {
        lcp[i] = pl.find_lcp(order[i], order[i + 1]);
    }
    ll ans = 0;
    {
        vector<vector<int>> turnoff(n + 1), turnon_gr(n + 1);
        for (int i = 1; i < sz(nww); i += 2) {
            int ml = result[i] / 2;
            turnoff[ml / 2 + 1].pb(pos[i / 2]);
        }
        for (int i = 0; i < n - 1; i++) {
            turnon_gr[lcp[i]].pb(i);
        }
        dsu d(n);
        for (int len = n - 1; len >= 0; len--) {
            for (int el : turnoff[len + 1]) {
                d.upd_sum(el, 1);
            }
            for (int el : turnon_gr[len + 1]) {
                d.merge(el, el + 1);
            }
            ans = max(ans, d.bs * 1ll * (2 * len + 1));
        }
    }
    {
        vector<vector<int>> turnoff(n + 1), turnon_gr(n + 1);
        for (int i = 2; i < sz(nww) - 1; i += 2) {
            int ml = result[i] / 2;
            turnoff[ml / 2 + 1].pb(pos[i / 2]);
        }
        for (int i = 0; i < n - 1; i++) {
            turnon_gr[lcp[i]].pb(i);
        }
        dsu d(n);
        for (int len = n - 1; len >= 0; len--) {
            for (int el : turnoff[len + 1]) {
                d.upd_sum(el, 1);
            }
            for (int el : turnon_gr[len]) {
                d.merge(el, el + 1);
            }
            ans = max(ans, d.bs * 1ll * (2 * len));
        }
    }
    cout << ans << '\n';
}

signed main() {
    int tt = 1;
    #ifdef LOCAL 
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
        cin >> tt;
    #else
        ios::sync_with_stdio(false); 
        cin.tie(0); cout.tie(0);
    #endif

    while (tt--) {
        solve();
    }

    return 0;
}