#include<iostream>
#include<algorithm>
#include<string>
#include<bitset>
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;
const int N = 1e6 + 16, mod = 1e9 + 7, base = 331;
const ll mod2 = (ll)mod * mod;
int n;
string s;
ll pw[N], hsh[N];
ll get(int l, int r) {
return (hsh[r] - hsh[l - 1] * pw[r - l + 1] + mod2) % mod;
}
int dp[N];
int main() {
cin.tie(NULL)->sync_with_stdio(false);
pw[0] = 1;
for (int i = 1; i < N; ++i)
pw[i] = pw[i - 1] * base % mod;
int test; cin >> test; while (test--) {
cin >> s; n = s.size();
s = " " + s;
for (int i = 1; i <= n; ++i)
hsh[i] = (hsh[i - 1] * base + s[i]) % mod;
fill(dp + 1, dp + n + 1, -N);
for (int i = 1; i <= n / 2; ++i)
for (int j = 1; j <= i; ++j)
if (get(j, i) == get(n - i + 1, n - j + 1))
dp[i] = max(dp[i], dp[j - 1] + 2);
int ans(1);
for (int i = 1; i <= n / 2; ++i) {
ans = max(ans, dp[i] + (i * 2 == n ? 0 : 1));
}
cout << ans << '\n';
}
}
/** /\_/\
* (= ._.)
* / >0 \>1
**/
/*
==================================================+
INPUT: |
--------------------------------------------------|
4
bonobo
deleted
racecar
racecars
--------------------------------------------------|
==================================================+
OUTPUT: |
--------------------------------------------------|
3
5
7
1
--------------------------------------------------|
==================================================+
*/
