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