#include<bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define mp make_pair #define fi first #define se second #define MASK(n) (1LL<<n) #define BIT(n,i) ((n>>i)&1) typedef pair<int,int> pii; typedef vector<int> vi; typedef pair<ll,int> pli; typedef pair<ll,ll> pll; const int M = 1e9+7; const int INF = 1e9+7; const ll INFLL = 1e18+7; template<class _,class __> bool minimize(_ & a, const __ b) { if (a > b) { a = b; return true; } return false; } template<class _,class __> bool maximize(_ & a,const __ b) { if (a < b) { a = b; return true; } return false; } void Add(int &a, const int b) { a += b; if (a >= M) a -= M; return; } void Diff(int &a, const int b) { a -= b; if (a < 0) a += M; return; } int mul(int a,int b) { return 1LL*a*b%M; } int diff(int a,int b) { Diff(a,b); return a; } int add(int a,int b) { Add(a,b); return a; } int FP(int base,int n) { if (n == 0) return 1; if (n == 1) return base; int tmp = FP(base,n/2); tmp = mul(tmp,tmp); if (n&1) tmp = mul(tmp,base); return tmp; } int Div(int a,int b) { return mul(a,FP(b,M-2)); } //------------------------------------------------------------ const int MaxN = 1e6+7; const int base = 301; int n; string s; struct Hashing { int H[MaxN]; int Pow[MaxN]; void Set(string & s) { int len = s.length(); Pow[0] = 1; for (int i=1;i<=len;i++) Pow[i] = mul(Pow[i-1],base); for (int i=1;i<=len;i++) { H[i] = mul(H[i-1],base); Add(H[i],s[i-1]); } } int Get(int r,int l) { return diff(H[r],mul(H[r-l],Pow[l])); } } HashS; namespace sub1 { bool check() { return true; } int f[MaxN]; void sol() { f[0] = 0; for (int i=1;i<=n/2;i++) { f[i] = -INF; for (int j=0;j<i;j++) { int l1 = j+1, r1 = i; int r2 = n - l1 + 1,l2 = n - r1 + 1; if (HashS.Get(r1,r1-l1+1) == HashS.Get(r2,r2-l2+1)) { maximize(f[i],f[j] + 1); } } } int res = 1; // cout << f[3] << '\n'; if (n&1) { for (int i=1;i<=n/2;i++) maximize(res,f[i]*2+1); } else { for (int i=1;i<n/2;i++) maximize(res,f[i]*2+1); maximize(res,f[n/2] * 2); } cout << res << '\n'; } } void sol() { cin >> s; n = s.length(); HashS.Set(s); if (sub1::check()) { sub1::sol(); return; } } int main() { // freopen("sixcup.inp","r",stdin); // freopen("sixcup.out","w",stdout); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t = 1; cin >> t; while (t--) sol(); }