#include <bits/stdc++.h>

using namespace std;
constexpr int INF = 1e9 + 7;

using vi = vector<int>;
#define sz(c) (int)c.size()
#define all(c) c.begin(),c.end()
#define rep(i, l, r) for(int i = l;i < r;++i)

struct SuffixArray {
    vi sa, lcp;

    SuffixArray(string &s, int lim = 256) { // or basic_string<int>
        int n = sz(s) + 1, k = 0, a, b;
        vi x(all(s)), y(n), ws(max(n, lim));
        x.push_back(0), sa = lcp = y, iota(all(sa), 0);
        for (int j = 0, p = 0; p < n; j = max(1, j * 2), lim = p) {
            p = j, iota(all(y), n - j);
            rep(i, 0, n) if (sa[i] >= j) y[p++] = sa[i] - j;
            fill(all(ws), 0);
            rep(i, 0, n) ws[x[i]]++;
            rep(i, 1, lim) ws[i] += ws[i - 1];
            for (int i = n; i--;) sa[--ws[x[y[i]]]] = y[i];
            swap(x, y), p = 1, x[sa[0]] = 0;
            rep(i, 1, n) a = sa[i - 1], b = sa[i], x[b] =
                        (y[a] == y[b] && y[a + j] == y[b + j]) ? p - 1 : p++;
        }
        for (int i = 0, j; i < n - 1; lcp[x[i++]] = k)
            for (k &&k--, j = sa[x[i] - 1];
                    s[i + k] == s[j + k];
        k++);
    }
};

struct s_tr {
    vector<int> s;
    vector<int> to_push;

    s_tr(int n) {
        s.resize(4 * n);
        to_push.resize(4 * n, INF);
    }

    void sets(int v, int x) {
        s[v] = min(s[v], x);
        to_push[v] = min(to_push[v], x);
    }

    void push(int v) {
        sets(v * 2 + 1, to_push[v]);
        sets(v * 2 + 2, to_push[v]);
        to_push[v] = INF;
    }

    void upd(int x) {
        sets(0, x);
    }

    int get(int v, int l, int r, int lq, int rq) {
        if (l >= rq || lq >= r || lq >= rq)return 0;
        if (l >= lq && r <= rq)return s[v];
        int m = (r + l) / 2;
        push(v);
        return max(get(v * 2 + 1, l, m, lq, rq), get(v * 2 + 2, m, r, lq, rq));
    }

    void set(int v, int l, int r, int k) {
        if (l + 1 == r) {
            s[v] = INF;
            return;
        }
        int m = (r + l) / 2;
        push(v);
        if (k < m)set(v * 2 + 1, l, m, k);
        else set(v * 2 + 2, m, r, k);
        s[v] = max(s[v * 2 + 1], s[v * 2 + 2]);
    }
};


array<vi, 2> manacher(const string &s) {
    int n = sz(s);
    array<vi, 2> p = {vi(n + 1), vi(n)};
    rep(z, 0, 2) for (int i = 0, l = 0, r = 0; i < n; i++) {
            int t = r - i + !z;
            if (i < r) p[z][i] = min(t, p[z][l + t]);
            int L = i - p[z][i], R = i + p[z][i] - !z;
            while (L >= 1 && R + 1 < n && s[L - 1] == s[R + 1])
                p[z][i]++, L--, R++;
            if (R > r) l = L, r = R;
        }
    return p;
}

void solve() {
    string s;
    cin >> s;
    int n = s.size();
    string t = s + (char) (1) + string(s.rbegin(), s.rend());
    auto SA = SuffixArray(t);
    vector<int> pal(n);
    {
        auto p = manacher(s);
        vector<vector<int>> x(n), y(n);
        set<int> chet, nechet;
        for (int i = 1; i <= n; ++i) {
            if (p[0][i]) {
                x[i - 1].push_back(i);
                if (i - 1 - p[0][i] >= 0)x[i - 1 - p[0][i]].push_back(i);
            }
        }
        for (int i = 0; i < n; ++i) {
            y[i].push_back(i);
            if (i - p[1][i] - 1 >= 0)y[i - p[1][i] - 1].push_back(i);
        }
        for (int i = n - 1; ~i; --i) {
            for (auto j: x[i]) {
                if (chet.count(j))chet.erase(j);
                else chet.insert(j);
            }
            for (auto j: y[i]) {
                if (nechet.count(j))nechet.erase(j);
                else nechet.insert(j);
            }
            if (chet.size())pal[i] = max(pal[i], 2 * (*chet.rbegin() - i));
            pal[i] = max(pal[i], 1 + 2 * (*nechet.rbegin() - i));
        }
    }
    vector<int> st(n), en(n);
    for (int i = 0; i < n; ++i) st[i] = !i || s[i] != s[i - 1] ? 1 : st[i - 1] + 1;
    for (int i = n - 1; ~i; --i) en[i] = i + 1 == n || s[i] != s[i + 1] ? 1 : en[i + 1] + 1;
    vector<int> val(n);
    for (int i = 0; i < n; ++i) {
        int l = pal[i];
        if (l % 2) {
            int mid = min(st[i + l / 2], en[i + l / 2]) * 2 - 1;
            mid = min(mid, l);
            val[i] = mid - 1 + (l - mid) / 2;
        } else {
            int mid = min(st[i + l / 2 - 1], en[i + l / 2]) * 2;
            mid = min(mid, l);
            val[i] = mid - 1 + (l - mid) / 2;
        }
    }
    vector<int> r(n, n - 1);
    vector<char> done(n);
    int res = 0;
    for(int k = 0;count(done.begin(),done.end(),0);++k){
        for (int i = 0; i < n; ++i) {
            if (!done[i] && pal[i] == r[i] - i + 1) {
                res = max(res, k + val[i]);
                done[i] = 1;
            }
        }
        vector<int> nr(n, -1);
        {
            s_tr tree(n);
            for (int i = 2; i < SA.sa.size(); ++i) {
                tree.upd(SA.lcp[i]);
                if (SA.sa[i] < n) {
                    int idx = SA.sa[i];
                    if (!done[idx])
                        nr[idx] = max(nr[idx], idx + tree.get(0, 0, n, idx + pal[idx], r[idx] + 1) - 1);
                } else {
                    int who = n - (SA.sa[i] - 1 - n) - 1;
                    tree.set(0, 0, n, who);
                }
            }
        }
        {
            s_tr tree(n);
            for (int i = SA.sa.size() - 1; i > 1; --i) {
                if (SA.sa[i] < n) {
                    int idx = SA.sa[i];
                    if (!done[idx])
                        nr[idx] = max(nr[idx], idx + tree.get(0, 0, n, idx + pal[idx], r[idx] + 1) - 1);
                } else {
                    int who = n - (SA.sa[i] - 1 - n) - 1;
                    tree.set(0, 0, n, who);
                }
                tree.upd(SA.lcp[i]);
            }
        }
        int mx = -1;
        for (int i = 0; i < n; ++i) {
            if (done[i])continue;
            bool ok = nr[i] - i + 1 >= pal[i];
            nr[i] = max(nr[i], mx);
            mx = max(mx, nr[i]);
            if (!ok) {
                res = max(res, k + val[i]);
                done[i] = 1;
            }
        }
        swap(nr, r);
    }

    cout << res << "\n";
}

int main() {
    cin.tie(0)->sync_with_stdio(false);
    int t;
    cin >> t;
    while (t--)solve();
}

// ccaaacc -> caaac -> aaa