#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) return;

        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);
    }
}