#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]});
// iota(all(ord), 0);
// vector<int> no(n);
// {
// vector<vector<int>> bs(n + 1);
// for (int i = 0; i < n; i++) bs[lol[ord[i]].second + 1].pb(ord[i]);
// int cur = 0;
// for (int i = 0; i <= n; i++) {
// for (int el : bs[i]) no[cur++] = el;
// }
// swap(no, ord);
// }
// {
// vector<vector<int>> bs(n);
// for (int i = 0; i < n; i++) bs[lol[ord[i]].first].pb(ord[i]);
// int cur = 0;
// for (int i = 0; i < n; i++) {
// for (int el : bs[i]) no[cur++] = el;
// }
// swap(no, ord);
// }
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;
}