#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define all(a) begin(a), end(a)
#define len(a) int((a).size())
// source: https://judge.yosupo.jp/submission/42086
#include <algorithm>
#include <cassert>
#include <cstring>
#include <functional>
#include <initializer_list>
#include <iostream>
#include <memory>
#include <queue>
#include <random>
#include <vector>
void SA_IS(const int *s, int *SA, int n, int K) {
// s 为字符串数组[0..n-1] 必须保证 s[n-1]=0 且为最小值
// SA 为存储后缀数组[0..n-1]
// n 为字符串长度
// K 为值域
bool *t = new bool[n]; // 类型数组
int *bkt = new int[K]; // 桶
int *bkt_l = new int[K];
int *bkt_r = new int[K];
int n1 = 0; // LMS-后缀的数量
int *p1; //按出现顺序存储所有 LMS-后缀的索引
#define is_S_type(x) (t[x])
#define is_L_type(x) (!t[x])
#define is_LMS_type(x) (is_S_type(x) && x != 0 && is_L_type(x - 1))
// 预处理每一个后缀的类型
t[n - 1] = true; // 0 为 S-型后缀且为 LMS-型后缀
for (int i = n - 2; i >= 0; --i) {
t[i] = (s[i] < s[i + 1] || (is_S_type(i + 1) && s[i] == s[i + 1]));
n1 += is_LMS_type(i + 1); // s[0] 必然不是 LMS-型后缀，不会影响
}
// 预处理桶的边界
for (int i = 0; i != K; ++i) bkt[i] = 0;
for (int i = 0; i != n; ++i) ++bkt[s[i]];
for (int i = 0, sum = 0; i != K; ++i) sum += bkt[i], bkt_r[i] = sum, bkt_l[i] = sum - bkt[i];
#define indecud_sort() \
do { \
for (int i = 0; i != K; ++i) bkt[i] = bkt_l[i]; \
for (int i = 0, j; i != n; ++i) \
if ((j = SA[i] - 1) >= 0 && is_L_type(j)) SA[bkt[s[j]]++] = j; \
for (int i = 0; i != K; ++i) bkt[i] = bkt_r[i]; \
for (int i = n - 1, j; i >= 0; --i) \
if ((j = SA[i] - 1) >= 0 && is_S_type(j)) SA[--bkt[s[j]]] = j; \
} while (0)
// 将所有 LMS-后缀放入 SA 对应桶的末尾并诱导排序
p1 = new int[n1];
for (int i = 0, j = 0; i != n; ++i) {
SA[i] = -1;
if (is_LMS_type(i)) p1[j++] = i;
}
for (int i = 0; i != K; ++i) bkt[i] = bkt_r[i];
for (int i = n1 - 1; i >= 0; --i) SA[--bkt[s[p1[i]]]] = p1[i];
indecud_sort();
int *s1 = new int[n1]; // 新的字符串
int *SA1 = new int[n1]; // 存储新的字符串排的后缀数组
for (int i = 0, j = 0; i != n; ++i)
if (is_LMS_type(SA[i])) SA1[j++] = SA[i]; // 存储 LMS-子串的相对顺序
int name = 0;
// 对所有 LMS-子串命名
for (int i = 0, prev = -1; i != n1; ++i) {
int pos = SA1[i];
for (int j = 0;; ++j) // 无需设置范围，因为 s[n-1]=0 为最小值且不会出现在其余位置
if (prev == -1 || s[pos + j] != s[prev + j] || is_S_type(pos + j) != is_S_type(prev + j)) {
prev = pos, ++name;
break;
} else if (j != 0 && (is_LMS_type(pos + j) || is_LMS_type(prev + j))) // 到末尾了停止比较
break;
SA[pos] = name - 1; // 利用 SA 暂时存储新字符串的 name
}
for (int i = 0; i != n1; ++i) s1[i] = SA[p1[i]];
if (name != n1)
SA_IS(s1, SA1, n1, name);
else
for (int i = 0; i != n1; ++i) SA1[s1[i]] = i;
for (int i = 0; i != K; ++i) bkt[i] = bkt_r[i];
for (int i = 0; i != n; ++i) SA[i] = -1;
for (int i = n1 - 1; i >= 0; --i) SA[--bkt[s[p1[SA1[i]]]]] = p1[SA1[i]];
indecud_sort();
delete[] SA1;
delete[] s1;
delete[] p1;
delete[] bkt_r;
delete[] bkt_l;
delete[] bkt;
delete[] t;
#undef is_S_type
#undef is_L_type
#undef is_LMS_type
#undef indecud_sort
}
std::vector<int> get_sa(const std::string &s) {
int len = s.size();
std::vector<int> SA(len + 1), s_cpy(len + 1);
for (int i = 0; i != len; ++i) s_cpy[i] = s[i];
s_cpy.back() = 0;
SA_IS(s_cpy.data(), SA.data(), len + 1, 128);
return std::vector<int>(SA.begin() + 1, SA.end());
}
struct suffix_array {
std::vector<int> order, suffix_position, lcp;
template<typename T>
suffix_array(T str = T()) {
int n = str.size() + 1;
order = get_sa(str);
order.insert(order.begin(), n - 1);
suffix_position.resize(n);
for (int i = 0; i < n; i++) {
suffix_position[order[i]] = i;
}
lcp.resize(n);
int current_lcp = 0;
for (int suffix = 0; suffix < n - 1; suffix++, current_lcp = current_lcp == 0 ? 0 : current_lcp - 1) {
int previous_suffix = order[suffix_position[suffix] - 1];
while (str[suffix + current_lcp] == str[previous_suffix + current_lcp])
current_lcp++;
lcp[suffix_position[suffix]] = current_lcp;
}
}
};
/*
* Zero based.
* Type T must have operator += T.
* Type T must have default constructor, which sets neutral value.
* Operation += must be commutative.
* For segment query type T must have operator -= T.
*/
template<typename T>
struct binary_indexed_tree {
std::vector<T> bit;
// Fills the array with default values.
binary_indexed_tree(int n = 0) : bit(n + 1) {}
int size() const {
return int(bit.size()) - 1;
}
// Adds delta at the position pos.
void add(int pos, T delta) {
for (pos++; pos < static_cast<int>(bit.size()); pos += pos & -pos) {
bit[pos] += delta;
}
}
// Returns the sum on the segment [0, pref].
T query(int pref) {
T sum = T();
for (pref++; pref > 0; pref -= pref & -pref) {
sum += bit[pref];
}
return sum;
}
// Returns the sum on the interval [l, r).
T query(int l, int r) {
if (r <= l) {
return T();
}
T res = query(r - 1);
res -= query(l - 1);
return res;
}
};
/*
* Zero based.
* Works for operations Op, such that Op(S) = Op(S \cup x), where x in S (like min, max, gcd...).
* Operation must be commutative.
*/
template<typename T, typename merge_t = std::function<T(T, T)>>
class sparse_table {
private:
std::vector<std::vector<T>> sparse;
const merge_t merge;
public:
sparse_table(const merge_t &merge) : merge(merge) {}
sparse_table(const std::vector<T> &a, const merge_t &merge) : merge(merge) {
const int n = a.size(), lg = std::__lg(std::max(1, n));
sparse.reserve(lg + 1);
sparse.push_back(a);
for (int level = 1; level <= lg; level++) {
sparse.push_back(std::vector<T>(n - (1 << level) + 1));
for (int i = 0; i < static_cast<int>(sparse[level].size()); i++) {
sparse[level][i] = merge(sparse[level - 1][i], sparse[level - 1][i + (1 << (level - 1))]);
}
}
}
sparse_table(const sparse_table &sparse) : sparse(sparse.sparse), merge(sparse.merge) {}
sparse_table& operator=(const sparse_table<T, merge_t> &another) {
sparse = another.sparse;
return *this;
}
// Returns result of merging elements on the interval [l, r).
T query(int l, int r) const {
assert(l < r);
const int level = std::__lg(r - l);
return merge(sparse[level][l], sparse[level][r - (1 << level)]);
}
};
/*
* Node must have default constructor.
* Node must have static function merge.
* Node must have .push and .clear_after_push methods.
*/
template<typename node>
class segtree {
private:
void build(int v, int vl, int vr) {
if (vr - vl <= 1)
return;
int vm = (vl + vr) >> 1;
build(v << 1, vl, vm);
build(v << 1 | 1, vm, vr);
tree[v] = node::merge(tree[v << 1], tree[v << 1 | 1]);
}
template<typename T>
void build(int v, int vl, int vr, const std::vector<T> &arr) {
if (vl == vr)
return;
if (vr - vl == 1) {
tree[v] = node(arr[vl]);
return;
}
int vm = (vl + vr) >> 1;
build(v << 1, vl, vm, arr);
build(v << 1 | 1, vm, vr, arr);
tree[v] = node::merge(tree[v << 1], tree[v << 1 | 1]);
}
template<typename... Args>
void _update(int v, int vl, int vr, int l, int r, Args&&... args) {
if (r <= vl || vr <= l)
return;
if (l <= vl && vr <= r) {
tree[v].apply(std::forward<Args>(args)..., vl, vr);
return;
}
int vm = (vl + vr) >> 1;
tree[v].push(tree[v << 1], vl, vm);
tree[v].push(tree[v << 1 | 1], vm, vr);
tree[v].clear_after_push();
_update(v << 1, vl, vm, l, r, std::forward<Args>(args)...);
_update(v << 1 | 1, vm, vr, l, r, std::forward<Args>(args)...);
tree[v] = node::merge(tree[v << 1], tree[v << 1 | 1]);
}
node _query(int v, int vl, int vr, int l, int r) {
if (l <= vl && vr <= r)
return tree[v];
int vm = (vl + vr) >> 1;
tree[v].push(tree[v << 1], vl, vm);
tree[v].push(tree[v << 1 | 1], vm, vr);
tree[v].clear_after_push();
if (r <= vm)
return _query(v << 1, vl, vm, l, r);
if (vm <= l)
return _query(v << 1 | 1, vm, vr, l, r);
return node::merge(_query(v << 1, vl, vm, l, r), _query(v << 1 | 1, vm, vr, l, r));
}
template<typename T>
int _find_first(int v, int vl, int vr, int from, const T &checker) {
if (vr <= from)
return n;
if (from <= vl && !checker(tree[v], vl, vr))
return n;
if (vr - vl == 1)
return vl;
int vm = (vl + vr) >> 1;
tree[v].push(tree[v << 1], vl, vm);
tree[v].push(tree[v << 1 | 1], vm, vr);
tree[v].clear_after_push();
int res = _find_first(v << 1, vl, vm, from, checker);
return res == n ? _find_first(v << 1 | 1, vm, vr, from, checker) : res;
}
template<typename T>
int _find_last(int v, int vl, int vr, int from, const T &checker) {
if (from <= vl)
return -1;
if (vr <= from && !checker(tree[v], vl, vr))
return -1;
if (vr - vl == 1)
return vl;
int vm = (vl + vr) >> 1;
tree[v].push(tree[v << 1], vl, vm);
tree[v].push(tree[v << 1 | 1], vm, vr);
tree[v].clear_after_push();
int res = _find_last(v << 1 | 1, vm, vr, from, checker);
return res == -1 ? _find_last(v << 1, vl, vm, from, checker) : res;
}
public:
int n;
std::vector<node> tree;
segtree(int n) : n(n), tree(4 * n, node()) {
build(1, 0, n);
}
template<typename T>
segtree(const std::vector<T> &arr) : n(arr.size()), tree(4 * n) {
build(1, 0, n, arr);
}
int size() const {
return n;
}
template<typename... Args>
void update(int l, int r, Args&&... args) {
if (r <= l)
return;
_update(1, 0, n, l, r, std::forward<Args>(args)...);
}
node query(int l, int r) {
assert(std::max(0, l) < std::min(n, r)); // or return node() in this case
return _query(1, 0, n, l, r);
}
// Trying to find first true on the interval [from, n).
// Returns n if not found.
template<typename T>
int find_first(int from, const T &checker) {
return _find_first(1, 0, n, from, checker);
}
// Trying to find last true on the interval [0, from).
// Returns -1 if not found.
template<typename T>
int find_last(int from, const T &checker) {
return _find_last(1, 0, n, from, checker);
}
};
struct node {
int mx = -1e9;
node() {}
void apply(ll delta, int, int) {
mx = delta;
}
void push(node&, int, int) {}
void clear_after_push() {}
static node merge(const node &left, const node &right) {
node res;
res.mx = max(left.mx, right.mx);
return res;
}
};
void solve(int /* test_num */) {
string s;
cin >> s;
int n = len(s);
auto t = s + "#";
auto reversed = s;
reverse(all(reversed));
t += reversed;
suffix_array sa(t);
auto merge_min = [](int x, int y) {
return x < y ? x : y;
};
sparse_table<int, decltype(merge_min)> sparse(sa.lcp, merge_min);
vector<int> dp(n, n - 1);
int ans = 0;
const int ITS = __lg(n) + 2;
for (int it = 1; it <= ITS; it++) {
segtree<node> tree(2 * n + 2);
int max_r = -1;
for (int l = 0; l < n; l++) {
while (max_r < dp[l]) {
max_r++;
int pos = sa.suffix_position[n + 1 + (n - 1 - max_r)];
tree.update(pos, pos + 1, max_r);
}
int lb = 0, rb = max_r - l + 1;
while (rb - lb > 1) {
int mid = (lb + rb) / 2;
int pos = sa.suffix_position[l];
int left;
{
int low = -1, high = pos;
while (high - low > 1) {
int mid2 = (low + high) / 2;
if (sparse.query(mid2 + 1, pos + 1) < mid) {
low = mid2;
} else {
high = mid2;
}
}
left = high;
}
int right;
{
int low = pos, high = 2 * n + 2;
while (high - low > 1) {
int mid2 = (low + high) / 2;
if (sparse.query(pos + 1, mid2 + 1) >= mid) {
low = mid2;
} else {
high = mid2;
}
}
right = low;
}
if (tree.query(left, right + 1).mx - mid + 1 > l) {
lb = mid;
} else {
rb = mid;
}
}
if (lb == 0) {
dp[l] = -1;
continue;
}
ans = max(ans, it);
dp[l] = l + lb - 1;
}
}
vector<int> nxt(n + 1, n);
for (int i = n - 2; i >= 0; i--) {
if (s[i] != s[i + 1]) {
nxt[i] = i + 1;
} else {
nxt[i] = nxt[i + 1];
}
}
vector<int> prev(n, -1);
for (int i = 1; i < n; i++) {
if (s[i] != s[i - 1]) {
prev[i] = i - 1;
} else {
prev[i] = prev[i - 1];
}
}
auto check = [&] (int l, int r) {
if (l >= r) return;
bool ok = true;
for (int d = 0; d <= r - l && ok; d++) {
ok &= s[l + d] == s[r - d];
}
if (!ok) continue;
int length = r - l + 1;
if (length % 2 == 1) {
int mid = (l + r) / 2;
int rr = nxt[mid] - 1;
int ll = prev[mid] + 1;
ll = max(ll, mid - (rr - mid));
rr = min(rr, mid + (mid - ll));
ans = max(ans, ITS + length / 2 + (rr - ll) / 2);
} else {
int mid = (l + r) / 2;
if (s[mid] != s[mid + 1]) {
ans = max(ans, ITS + length / 2);
} else {
int ll = prev[mid] + 1;
int rr = nxt[mid] - 1;
ll = max(ll, mid - (rr - mid - 1));
rr = min(rr, mid + 1 + (mid - ll));
ans = max(ans, ITS + length / 2 + (rr - ll + 1) / 2);
}
}
};
for (int l = 0; l < n; l++) {
if (dp[l] == -1) {
continue;
}
int r = dp[l];
check(l, r);
check(l + 1, r);
check(l, r - 1);
}
cout << ans << '\n';
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int tests;
cin >> tests;
for (int test_num = 1; test_num <= tests; test_num++) {
solve(test_num);
}
}