#include <bits/stdc++.h> #define int long long #define FOR(i,a,b) for (long long i = (a), _b = (b); i <= _b; i++) #define FORD(i,b,a) for (long long i = (b), _a = (a); i>= _a; i--) #define REP(i,n) for( long long i = 0, _n = (n); i < _n; i++) #define all(v) (v).begin(),(v).end() #define fi first #define se second #define MASK(i) (1<<(i)) #define BIT(x,i) ((x) >> (i) & 1) using namespace std; template<class X, class Y> bool minimize(X &x, const Y &y) { if (x > y) { x = y; return true; } else return false; } template<class X, class Y> bool maximize(X &x, const Y &y) { if (x < y) { x = y; return true; } else return false; } const int N = 1e6+5; const int base = 256; int mod[2] = {(int)1e9+7,(int)998244353}; int pw[2][N], HASH[2][N]; unsigned getHash(int l,int r){ int u = (HASH[0][r] - HASH[0][l-1] * pw[0][r-l+1] + mod[0] * mod[0]) % mod[0]; int v = (HASH[1][r] - HASH[1][l-1] * pw[1][r-l+1] + mod[1] * mod[1]) % mod[1]; //cout << u << ' ' << v << '\n'; return (u << 30ll) | v; } signed main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int t; cin >> t; pw[0][0] = 1; pw[1][0] = 1; FOR(i,1,N-1) pw[0][i] = pw[0][i-1] * base % mod[0], pw[1][i] = pw[1][i-1] * base % mod[1]; while(t--){ string s; cin >> s; int n = s.size(); if(n <= 15){ int ans = 0; REP(mask, MASK(n)){ string t=""; vector<string> ok; REP(i,n) { t += s[i]; if(BIT(mask,i)){ ok.push_back(t); t = ""; } } if(t.size()) ok.push_back(t); int m = ok.size(); bool palin = true; int i = 0, j = m - 1; while(i <= j){ if(ok[i] != ok[j]) palin = false; i++;j--; } if(palin) { maximize(ans,m); } } cout << ans << '\n'; continue; } s = " " + s; FOR(i,1,n) HASH[0][i] = (HASH[0][i-1] * base + s[i]) % mod[0]; FOR(i,1,n) HASH[1][i] = (HASH[1][i-1] * base + s[i]) % mod[1]; int i = 1, j = n; int ans = 0; while(i < j){ int u = i, v = j; while(getHash(i,u) != getHash(v,j) && u < n && v > 1) u++, v--; if(i != v && u != j) ans += 2; else ans++; i = u+1, j = v-1; if(i == j) { ans ++; break; } } cout << ans << '\n'; } cerr << "\nTime elapsed: " << clock() * 1.000 / CLOCKS_PER_SEC << " ms.\n"; return 0; }