#include<bits/stdc++.h>
using namespace std;
const int mxN = 1e6 + 6;
const int base = 53;
const int MOD = 1e9 + 7;
int H[mxN], P[mxN];
int get_hash(int l, int r){
return (1LL * H[r] - 1LL * H[l - 1] * P[r - l + 1] % MOD + MOD) % MOD;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
P[0] = 1;
for(int i = 1;i < mxN;++i){
P[i] = 1LL * P[i - 1] * base % MOD;
}
int t;
cin >> t;
while(t--){
string str;
cin >> str;
int n = (int)str.size();
str = '$' + str;
for(int i = 1;i <= n;++i){
H[i] = (1LL * H[i - 1] * base % MOD + (str[i] - 'a' + 1)) % MOD;
}
vector<int>dp(n + 1, 1);
dp[n / 2] = n % 2;
for(int i = n / 2 - 1;i >= 0;--i){
for(int j = 1;2 * j <= n - 2 * i;++j){
// cout << i << ": " << j << "\n";
if(get_hash(i + 1, i + j) == get_hash(n - i - j + 1, n - i))dp[i] = max(dp[i], dp[i + j] + 2);
}
// cout << i << ": dp = " << dp[i] << '\n';
}
cout << dp[0] << '\n';
}
}
