#include <iostream>
#include <cstring>
using namespace std;
string s;
int N;
int m[1000100];
int solve(int n){
if(N-n-1<n)
return 0;
if(m[n]!=-1)
return m[n];
int sol = 1;
for(int x=N-n-1; x>=n; x--){
if(s[x]==s[n]){
//possible beginning of palindromic sequence
bool m = 1;
for(int y=0; y+x<=N-n-1; y++){
if(s[y+x]!=s[n+y])
m = 0;
}
if(m&&x!=n){
sol = max(sol, 2+solve(N-x));
break;
}
}
}
return m[n] = sol;
}
int main(){
int T; cin>>T;
while(T--){
cin>>s;
N = s.length();
memset(m, -1, sizeof(m));
cout << solve(0) << endl;
}
return 0;
}
