#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())

template<int SZ>
struct hash_t {
    inline static bool initialized = false;
    inline static int MOD[SZ], BASE[SZ];
    inline static std::vector<int> POWER[SZ];

    static void initialize() {
        assert(!initialized);
        initialized = true;
        std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
        for (int i = 0; i < SZ; i++) {
            auto is_prime = [&](int x) {
                for (int i = 2; i * i <= x; i++)
                    if (x % i == 0)
                        return false;

                return true;
            };

            MOD[i] = int(8e5) + rng() % int(2e8 + 228);
            while (!is_prime(MOD[i]))
                MOD[i]++;

            BASE[i] = rng() % MOD[i];
            if (!(BASE[i] & 1))
                BASE[i]++;

            POWER[i].push_back(1);
        }
    }

    static void ensure(int n) {
        assert(initialized);
        if (int(POWER[0].size()) >= n)
            return;

        for (int i = 0; i < SZ; i++)
            for (int j = POWER[i].size(); j < n; j++)
                POWER[i].push_back(int64_t(POWER[i].back()) * BASE[i] % MOD[i]);
    }

    int length;
    std::array<int, SZ> h;

    hash_t() : length(0) {
        h.fill(0);
        if (!initialized)
            initialize();
    }

    template<typename T>
    hash_t(const T &value, int length = 1) : length(length) {
        if (!initialized)
            initialize();

        ensure(length);
        h.fill(0);
        for (int i = 0; i < SZ; i++)
            for (int j = 0; j < length; j++) {
                h[i] += int64_t(value + 1) * POWER[i][j] % MOD[i];
                if (h[i] >= MOD[i])
                    h[i] -= MOD[i];
            }
    }

    hash_t<SZ>& operator+=(const hash_t<SZ> &x) {
        assert(initialized);
        ensure(x.length + 1);
        for (int i = 0; i < SZ; i++)
            h[i] = (int64_t(h[i]) * POWER[i][x.length] + x.h[i]) % MOD[i];

        length += x.length;
        return *this;
    }

    hash_t<SZ>& operator-=(const hash_t<SZ> &x) {
        assert(initialized);
        assert(x.length <= length);
        ensure(length - x.length + 1);
        for (int i = 0; i < SZ; i++) {
            h[i] -= int64_t(x.h[i]) * POWER[i][length - x.length] % MOD[i];
            if (h[i] < 0)
                h[i] += MOD[i];
        }
        length -= x.length;
        return *this;
    }

    bool operator==(const hash_t<SZ> &x) const {
        if (length != x.length)
            return false;

        return h == x.h;
    }

    bool operator<(const hash_t<SZ> &x) const {
        if (length != x.length)
            return length < x.length;

        return h < x.h;
    }

    friend hash_t<SZ> operator+(const hash_t<SZ> &left, const hash_t<SZ> &right) {
        return hash_t<SZ>(left) += right;
    }

    friend hash_t<SZ> operator-(const hash_t<SZ> &left, const hash_t<SZ> &right) {
        return hash_t<SZ>(left) -= right;
    }
};

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

/*
 * 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;
    int min_lcp_left = 1e9;
    int min_lcp_right = 1e9;

    node() {}

    node(int x) {
        min_lcp_left = x;
    }

    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);
        res.min_lcp_left = min(left.min_lcp_left, right.min_lcp_left);
        res.min_lcp_right = min(left.min_lcp_right, right.min_lcp_left);
        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);

    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(sa.lcp);

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

            if (max_r <= l) {
                dp[l] = -1;
                continue;
            }

            int max_len = 0, pos = sa.suffix_position[l];

            {
                int cur_max = -1e9, cur_lcp = 1e9;

                tree.find_first(pos + 1, [&](const node &nd, int, int) {
                    int cur_len = min(cur_lcp, nd.min_lcp_left);
                    if (max(cur_max, nd.mx) - cur_len + 1 <= l) {
                        cur_lcp = cur_len;
                        cur_max = max(cur_max, nd.mx);
                        max_len = max(max_len, cur_max - l);
                        return false;
                    }
                    max_len = max(max_len, cur_len);
                    return true;
                });
            }

            {
                int cur_max = -1e9, cur_lcp = sa.lcp[pos];

                tree.find_last(pos, [&](const node &nd, int, int) {
                    int cur_len = min(cur_lcp, nd.min_lcp_right);
                    if (max(cur_max, nd.mx) - cur_len + 1 <= l) {
                        cur_lcp = min(cur_len, nd.min_lcp_left);
                        cur_max = max(cur_max, nd.mx);
                        max_len = max(max_len, cur_max - l);
                        return false;
                    }
                    max_len = max(max_len, cur_len);
                    return true;
                });
            }

            if (max_len == 0) {
                dp[l] = -1;
                continue;
            }
            ans = max(ans, it);
            dp[l] = l + max_len - 1;
        }

        int pmax = -1;
        for (int l = 0; l < n; l++) {
            pmax = max(pmax, dp[l]);
            dp[l] = pmax;
        }
    }

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

    using Hash = hash_t<2>;
    vector<Hash> phash(n + 1);
    for (int i = 0; i < n; i++) {
        phash[i + 1] = phash[i] + Hash(s[i]);
    }

    vector<Hash> shash(n + 1);
    for (int i = n - 1; i >= 0; i--) {
        shash[i] = shash[i + 1] + Hash(s[i]);
    }

    for (int l = 0; l < n; l++) {
        if (dp[l] <= l) {
            continue;
        }

        int r = dp[l];
        if (phash[r + 1] - phash[l] != shash[l] - shash[r + 1]) {
            continue;
        }

        int length = r - l + 1;
        if (length % 2 == 1) {
            int mid = (l + r) / 2;
            int rr = min(r, nxt[mid] - 1);
            int ll = mid - (rr - mid);
            ans = max(ans, ITS + length / 2 + (rr - ll) / 2);
        } else {
            int mid = (l + r) / 2;
            int rr = min(r, nxt[mid] - 1);
            int ll = mid - (rr - (mid + 1));
            ans = max(ans, ITS + length / 2 + (rr - ll - 1) / 2);
        }
    }

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